2图论 函数9 7.ppt

* * 复习： 1、函数定义：设X、Y为非空集合，f ? X×Y是X到Y的二元关系 满足：对每个x ?X,都存在一个唯一的y?Y 使x,y ?f则称关系f为X到Y的函数（映射） 记作：f: X ? Y 1函数f于一般的X到Y的关系之间有二个区别： a、存在性：要且对任一x ? X,均作为f中序偶的第一成员 x,y ?f 即Dom(f)=X b.唯一性： 对于每个x,存在唯一的y,使x,y?f 2若f是A到B的函数， Dom(f)= A 集合A称为f的定义域 Ran(f)称为f的值域，B成为函数f的陪域 Ran(f) ? B 3若f是A到B的函数,A1 ? A, B1 ? B f(A1)={f(x)|x ?A1 }=B1 为A1在f下的像(是B的子集） f(A)为函数的像 f-1(B1)={x| x ?A ∧f(x)?B1}为B1在f下的完全原像(是A的子集) 4函数的基数：设A、B为非空集合，#A=m, #B=n 所有定义在A到B上的函数用集合BA ={f | f是A到B的函数} 当AB中为空集的情况：??=B?={?}、 ?A = ? 2、几种重要性质的函数 1、定义： 设f:A ? B,函数： 若Ran(f)=B 则称f为映满函数（满函数） f(A)=B 陪域与函数的像（值域）相等 注：即： ?y ? B , ?x ? A 使x,y ? f f是满函数的必要条件是｜B｜≤｜A｜ 若Ran(f)?B 是B的真子集，则称f为映入函数 f:A ? B若： ?x1 x2 ?A, 当x1 ≠ x2时有，f(x1) ≠ f(x2) 则称f为单射函数 f为单函数的必要条件｜B｜≥｜A｜ f:A ? B 若f即是单射函数又是满射函数，则称 f为双射函数. 注：1 f单射：必要条件： ｜B｜≥｜A｜ f满射：必要条件： ｜B｜≤｜A｜ f双射必要条件： ｜B｜＝｜A｜ 自然映射： R是X上的等价关系，g:X ? X/R , ?x ?X,g(x)=[x]R g是X到商集的自然映射，是一个满函数 特征函数：设A为集合，对于任意的A’?A,A’的特征函数ΧA’ ：A ? {0,1}定义为 ΧA’ (a)= 1 a ∈A’ 0 a ∈A-A’ 可以用特征函数来标记不同的子集合 §8.2 函数的复合与反函数 一、函数的复合即为前面的关系的复合。 1：设f是X到Y的函数，g是Y到Z的函数 复合关系：fog={x,z| ?y(y?Y∧x,y?f ∧y,z?g)} 称为f与g的复合函数 注：1定义中,?y(x,y?f ∧y,z?g)说明： Ran(f) ? Dom(g) gof 不空 2 fog是X到Z的函数 且 ?x?X, fog (x) = g( f(x) ) 说明，fog是X到Z的函数，要验证两点 1〉存在性：因为f是X到Y的函数, ?x?X, f(x)存在 且f(x) ? Ran(f) , Ran(f) ? Y,即：f(x)=y 又因为：g是Y到Z的函数，那么，对于f (x) ? Y，有 g(f(x))存在，使： g(f(x)) ?Z,即 x, g(f(x)) ? fog 2唯一性： ?x ?X, fog (x) ? Z 若不唯一，若有：z1与z2 ?Z使：fog (x)= z1, fog (x)= z2 即：x, z1 ? fog 且 x,z2 ? fog 存在y1使f(x)=y1且z1 =g(y1) 存在y2使f(x)=y2且z2 =g(y2) 因为f是函数， 设 y1 =y2 = y 故有： g(y)= z1 g(y)= z2 z1 ≠ z2 ， y在g下有二个象点，这与g是函数矛盾 所以z1 = z2 例：X={1,2,3,4} Y={a,b,c,d,e} Z={x,y,z} f={1,b,2,a,3,c,4,e} g={a,x,b,y,c,z,d,z,e,y} fog={1,y,2,x,3,z,4