离散数学期末复习大纲

1、复习大纲复习大纲一、关系的概念一、关系的概念1 1、关系的定义、关系的定义 集合集合A A到到B B的二元关系定义：设的二元关系定义：设A A，B B为集合，为集合， AxBAxB的任何子集的任何子集所确定的二元关系叫做从所确定的二元关系叫做从A A到到B B的二元关系的二元关系 当当A AB B时则叫做时则叫做A A上的二元关系上的二元关系2 2、关系的表示、关系的表示 1 1）集合表示）集合表示 R=x R=| P(x,y) y| P(x,y) 2 2）关系矩阵表示：有穷集合）关系矩阵表示：有穷集合A A上的二元关系可用上的二元关系可用布尔矩阵表示布尔矩阵表示 3 3）关系图）关系图G G

2、R R表示：表示： 以以A A中的元素为结点，若中的元素为结点，若 R R，则从到画一条有向弧，则从到画一条有向弧3 3、关系的运算、关系的运算 1 1）关系的一般集合的运算：）关系的一般集合的运算：并、交、相对补、补及对称差并、交、相对补、补及对称差 2 2）关系的逆运算）关系的逆运算 R R-1-1 x | y | yR xR 3 3） 关系的复合运算关系的复合运算 1 1）定义：设）定义：设F F，G G为二元关系，为二元关系，G G对对F F的右复合记作的右复合记作F o G F o G ， F o G F o G x | y | t (x t (F F G )yG )等价关系部分复习

3、等价关系部分复习 4）关系的幂运算）关系的幂运算 定义：设定义：设R为为A上的关系，上的关系，n为自然数，则为自然数，则R的的n次幂定义为：次幂定义为： (1) R0 | xA = IA (2) Rn+1 R n o R 即对于即对于A上的任何关系上的任何关系Rl和和R2都有都有 R10 R20 IA 性质性质: (类似于数的幂运算性质类似于数的幂运算性质) Rm o Rn = Rm+n ( Rm ) n = Rmn 4 4、关系的性质、关系的性质关系的性质主要有以下五种：关系的性质主要有以下五种：自反性，反自反性，对称性，反对称性和传递性自反性，反自反性，对称性，反对称性和传递性 (1) (

4、1) 若若 x( xA xx( xA R)xR)，则称，则称R R在在A A上是自反的上是自反的 具有自反性的关系矩阵的特征是：具有自反性的关系矩阵的特征是：主对角线上元素均为主对角线上元素均为1 1 具有自反性的关系图的特征是：具有自反性的关系图的特征是：每个结点均有环每个结点均有环 (2) (2) 若若x ( xA xx ( xA R)xR) ，则称，则称R R在在A A上是反自反的上是反自反的 具有反自反性的关系矩阵的特征是：具有反自反性的关系矩阵的特征是：主对角线上元素均为主对角线上元素均为0 0 具有自反性的关系图的特征是：具有自反性的关系图的特征是：每个结点均没有环每个结点均没有环

5、 （3 3）若）若 x x y y（x x，y A xy A R R RxR） 则称则称R R为为A A上的对称的关系上的对称的关系 具有对称性的关系矩阵的特征是：具有对称性的关系矩阵的特征是：是对称矩阵是对称矩阵 具有对称性的关系图的特征是：具有对称性的关系图的特征是：两个互异结点之间有弧必有方向相反的两条两个互异结点之间有弧必有方向相反的两条 （4 4）若）若 x x y y（x x，y A xy A R R RxR x = y x = y） 则称则称R R为为A A上的反对称的关系上的反对称的关系 具有反对称性的关系矩阵的特征是：具有反对称性的关系矩阵的特征是：是非对称矩阵是非对称矩阵

6、具有反对称性的关系图的特征是：具有反对称性的关系图的特征是：两个互异结点之间有弧仅有一条两个互异结点之间有弧仅有一条（5 5）若）若x xy yz(xz(x，y y，zA xzA R R R R R )zR )， 则称则称 R R为为A A上传递的关系。上传递的关系。 以上性质的定义中均使用了条件语句，当前件为假时，该语句为真。故当关系以上性质的定义中均使用了条件语句，当前件为假时，该语句为真。故当关系R R不满足某个性质定义前件时，就可以确定不满足某个性质定义前件时，就可以确定R R满足该性质。满足该性质。二、二、等价关系与划分等价关系与划分1 1、等价关系定义：设、等价关系定义：设R R为

7、非空集合上的关系为非空集合上的关系 如果如果R R是自反的是自反的、对称的对称的和和传递的传递的，则称，则称R R为为A A上的等价关系。上的等价关系。 设设R R是一个等价关系，若是一个等价关系，若x Ry R，称，称x x等价于等价于y y，记作，记作x x y y 注：注：1 1）R R是等价关系必须是等价关系必须同时满足三个性质同时满足三个性质 2)R 2)R是等价关系的矩阵特征和图特征是等价关系的矩阵特征和图特征2 2、典型例子：定义整数集上的关系、典型例子：定义整数集上的关系R R： R Rx | xy | x，yA x y(mod 5) yA x y(mod 5) 其中其中x y

8、(mod 5) x y(mod 5) 叫做叫做x x与与y y模模5 5相等相等，即，即x x除以除以5 5的余数与的余数与y y除以除以5 5的的余数相等余数相等3 3、等价类、等价类 1) 1)等价类定义：设等价类定义：设R R为非空集合为非空集合A A上的等价关系，上的等价关系，xAxA，令，令 x R y | y A x R y 或或 R 称称xxR R为为x x关于关于R R的等价类，简称为的等价类，简称为x x的等价类，简记为的等价类，简记为xxR R 注：注：xxR R是由是由A A中有与中有与x x有关系有关系R R 的元素组成的元素组成 （A A中所有与中所有与x x等价的元

9、素等价的元素构成的集合）即所有与构成的集合）即所有与x x 成为序对的成成为序对的成员构成。员构成。 等价类的代表等价类的代表 x x R R可以是该集合内的可以是该集合内的任何元素任何元素4、等价类的性质、等价类的性质设设R为非空集合为非空集合A上的上的等价关系等价关系，则，则1 xA，x R 是是A的非空子集的非空子集2 x，yA，如果，如果 xRy ，则，则 x R y R3 x，yA，如果，如果x与与y不具有关系不具有关系R，则，则x R y R = 4 xR | x A= A 三个定义等价：三个定义等价： xRy x R y R xy 问题：同一集合上的等价关系的并及交是否还是等价关

10、系？问题：同一集合上的等价关系的并及交是否还是等价关系？5、商集、商集 1）商集定义：设）商集定义：设R为非空集合为非空集合A上的等价关系，以上的等价关系，以R的的所有等价所有等价类作为元素的集合类作为元素的集合称为称为A关于关于R的商集，记作的商集，记作AR， 即即 AR x R | xA 由由A上等价关系上等价关系R的的所有不同等价类所有不同等价类构成的一个新集合构成的一个新集合6 6、集合划分的定义、集合划分的定义 设设A A为非空集合，若为非空集合，若A A的子集构成的集合族的子集构成的集合族 ( ( p(A) p(A) 是是A A的子集构成的集合的子集构成的集合) )满足下面的条件：

11、满足下面的条件： 1) 1) 不属于不属于 （不空）（不空） 2 2 x xy(xy(x，y x y x y = y x y x y = ) ) 互异互异 3 = A 3 = A 则称则称 是是A A的一个划分，称的一个划分，称 中的元素为中的元素为A A的划分块的划分块集合集合A A的一个的一个划分划分与集合与集合A A上的一个上的一个等价关系等价关系R R的等价类的等价类的关系：的关系：1 1）由等价关系）由等价关系R R所确定的集合所确定的集合A A的的商集商集 A AR R是集合是集合A A的的一个划分一个划分 集合集合A A上的一个上的一个等价关系等价关系R R与集合与集合A A上的

12、一个划分上的一个划分是一一对应关系是一一对应关系2 2）集合集合A A的不同划分的不同划分对应集合对应集合A A上的上的不同等价关系不同等价关系 对于集合对于集合A A的任何的任何一个划分一个划分均可确定均可确定A A上的上的一个等价关系一个等价关系R R 由由R R确定的关于确定的关于A A的商集等于此划分的商集等于此划分 需要掌握：给定需要掌握：给定A A上等价关系上等价关系R R确定确定A A的一个划分（即确定商集）的一个划分（即确定商集） 给定给定A A的一个划分的一个划分确定确定A A上的一个等价关系上的一个等价关系R R 有限集合上的所有等价关系（即有限集合的所有不同划分）有限集合

13、上的所有等价关系（即有限集合的所有不同划分）习题类型：习题类型： p133 33 p133 33、3636、4040 例：设例：设A A 1 1，2 2，3 3 求求A A上的所有等价关系上的所有等价关系 由于由于A A上的等价关系与上的等价关系与A A上的划分是一一对上的划分是一一对应关系，可从对应关系，可从对A A的划分来确定相应的等价关系的划分来确定相应的等价关系 三、函数：三、函数：作为作为特殊的二元关系特殊的二元关系来表示来表示1 1、函数定义：设、函数定义：设X X、Y Y为非空集合，为非空集合，f f X XY Y是是X X到到Y Y的二元关系的二元关系 满足：对每个满足：对每个

14、x x X,X,都存在一个唯一的都存在一个唯一的y y Y Y 使使 f f则称关系则称关系f f为为X X到到Y Y的函数（映射）的函数（映射） 记作：记作：f: X f: X Y Y a a、存在性存在性：要且对任一：要且对任一x x X, X, f f 即即Dom(f)=XDom(f)=X b. b.唯一性唯一性：对于每个：对于每个x,x,存在唯一的存在唯一的y y, ,使使 f f2 2、若、若f f是是A A到到B B的函数，的函数，Dom(f)= A Dom(f)= A 集合集合A A称为称为f f的的定义域定义域， B B成为函数成为函数f f的陪域，的陪域，Ran(f) Ran

15、(f) B, Ran(f) B, Ran(f)称为称为f f的值域的值域3 3、 若若 f ,f ,可记为可记为y=f(x),y=f(x),称称y y为为x x在在f f下的下的象点象点。 x x为为y y在在f f下的原象下的原象( (也可记为也可记为 x=f-1(y) x=f-1(y) ）。）。 Ran(f) Ran(f)称为称为函数的像函数的像 记为：记为： Ran(f) Ran(f) = f(A)= f(A) =y| y =y| y B B x( xx( x A A y=f(x) ) y=f(x) ) 4 4、若、若f f是是A A到到B B的函数的函数,A1 ,A1 A, B1 A,

16、 B1 B B f(A1)=f(A1)=f(x)|x f(x)|x A1 A1 =B1=B1 为为A1A1在在f f下的像下的像( (是是B B的子集）的子集） f(A) f(A)为函数的像为函数的像 f f-1-1(B1)=x| x (B1)=x| x A A f(x)f(x) B1B1 为为B1B1在在f f下的下的完全原像完全原像( (是是A A的子集的子集) ) A1 A1 A A f(A1) f(A1) B B 的完全原像的完全原像 f-1(f(A1) f-1(f(A1)是是A A的子集的子集习题类型：习题类型： P160 1 P160 1、 3 3、(b(b）对其中）对其中1 1道

17、题熟悉即可道题熟悉即可5 5、 所有定义在所有定义在A A到到B B上的函数上的函数 用集合用集合B BA A =f | f =f | f是是A A到到B B的函数的函数 习题八习题八 2 26 6、设、设f:A f:A B, B,函数：函数： 1 1）若）若Ran(f)=B Ran(f)=B 则称则称f f为为满函数（满函数满函数（满函数）f(A)=B f(A)=B 即：即： y y B , B , x x A A 使使 f f f f是满函数的是满函数的必要条件必要条件是是 B BA A 2 2）f:A f:A B B 若若: : x1 x2 x1 x2 A,A,当当x1x2x1x2时有时

18、有,f(x1)f(x2),f(x1)f(x2) 则称则称f f为单射函数为单射函数 f f为单函数的为单函数的必要条件必要条件 B BA A 3 3） f:A f:A B B 若若f f即是单射函数又是满射函数，则称即是单射函数又是满射函数，则称f f为双射函数为双射函数. . f f双射必要条件：双射必要条件： B BA A 当当f f是有限集合是有限集合A A上的单函数时上的单函数时 则则f f必是满函数（双射函数）必是满函数（双射函数）习题类型：习题八习题类型：习题八 5 5、10107 7、特殊函数、特殊函数1 1）常值函数：）常值函数： f:X f:X Y Y， x x X f(x)

19、=yX f(x)=y2 2）恒等函数）恒等函数 ：Ix: Ix: X X X X x f(x)=x x f(x)=x 双射函数双射函数 性质：性质： f f是是X X Y Y的函数的函数 f f Ix=Iy Ix=Iy f f3 3）自然映射：）自然映射：R R是是X X上的等价关系，上的等价关系，g:X g:X X/R , X/R , x x X,g(x)=xX,g(x)=xR R g g是是X X到商集的自然映射，是一个满函数到商集的自然映射，是一个满函数 8 8、函数的复合、函数的复合1 1）设）设f f是是X X到到Y Y的函数，的函数，g g是是Y Y到到Z Z的函数的函数 复合关系

20、：复合关系：fog=| fog=| y(yy(y Y Y f f g)g) 称为称为f f与与g g的复合函数的复合函数 fog fog是是X X到到Z Z的函数，且的函数，且 x x X, X, fog (x) = g( f(x) )fog (x) = g( f(x) ) 复合运算不满足交换律（与一般关系相同）复合运算不满足交换律（与一般关系相同） 若若f f是是X X上的函数，上的函数， f f f = f 2 f = f 2 fn fn 幂函数幂函数2 2）三类重要性质函数的复合性质）三类重要性质函数的复合性质证明的过程要理解证明的过程要理解 f:X f:X Y Y函数，函数， g:Y

21、g:Y Z Z函数函数 若若 f f g g 存在存在 i f i f与与g g均为满函数均为满函数 ， f f g g也是满函数也是满函数 ii f ii f与与g g均为单函数，均为单函数， f f g g也是单函数也是单函数 iii f iii f与与g g均为双射函数，均为双射函数， f f g g 也是双射函数也是双射函数如果如果 f f g g是单函数，能否确定是单函数，能否确定f f与与g g均是单函数？均是单函数？如果如果 f f g g是满函数，能否确定是满函数，能否确定f f与与g g均是满函数？均是满函数？习题类型：习题八习题类型：习题八 16 16、1818、2222、

22、26269 9、反函数、反函数1 1）定义：设）定义：设f:X f:X Y Y 的双射函数的双射函数则：则：f f的逆关系的逆关系f f称为：称为：f f的反函数，记为：的反函数，记为：f f-1-1 若函数若函数f f存在反函数，则称存在反函数，则称f f是可逆函数。是可逆函数。11并非任何函数都是可逆函数并非任何函数都是可逆函数22若若f f是可逆函数，则是可逆函数，则f f一定是双射函数一定是双射函数3f 3f 是是X X Y Y 的双射函数，则的双射函数，则f f是可逆函数是可逆函数f f-1-1存在存在 且且f f-1-1是是Y Y X X的双射函数。的双射函数。44若若f f是是

23、X X到到Y Y 的可逆函数，的可逆函数， g g是是Y Y 到到Z Z的可逆函数的可逆函数 f f g g是可逆函数，且是可逆函数，且(f g) -1 = g -1 f-1 f f-1= ？ f-1 f=？四、图的基本概念四、图的基本概念1 1、图的定义：一个无向图是一个有序的二元组、图的定义：一个无向图是一个有序的二元组 V E ，记作，记作G G，其中，其中(1) (1) V V 称为顶点集，其元素称为顶点或结点称为顶点集，其元素称为顶点或结点(2) (2) E E称为边集称为边集，它是，它是无序积无序积V VV V的多重子集，其元素称为无向边，简称为边的多重子集，其元素称为无向边，简称

24、为边 定义定义2 2 一个有向图是一个有序的二元组一个有向图是一个有序的二元组VE，记作，记作D D，其中，其中(1) V (1) V 称为顶点集，其元素称为顶点或结点称为顶点集，其元素称为顶点或结点(2)E(2)E为边集，它是为边集，它是笛卡儿积笛卡儿积 V VV V的有穷多重子集，其元素称为有向边的有穷多重子集，其元素称为有向边( (弧弧) )2 2、有关图的术语、有关图的术语1 1）用）用G G表示无向图，表示无向图，D D表示有向图有时用表示有向图有时用V(G)V(G)，E(G)E(G)分别表示分别表示G G的顶点集和边集的顶点集和边集2 2）用）用 V(G)V(G) ，E(G)E(G

25、)分别表示分别表示G G的顶点数和边数的顶点数和边数( (有向图类似）有向图类似） 若若V(G)V(G) n n，则称，则称G G为为n n阶图。对有向图可做类似规定阶图。对有向图可做类似规定3 3）在图）在图G G中，若中，若边集边集E(G)E(G)，则称，则称G G为为零图零图 若若G G为为n n阶图，则称阶图，则称G G为为n n阶零图阶零图，记作，记作N Nn n，特别是称，特别是称N N1 1为为平凡图平凡图4) 4) 常用常用e ek k表示无向边表示无向边(vi(vi，vj)( vj)( 或有向边或有向边vi ) vj ) 设设G GV E 为无向图，为无向图，e ek k =

26、 (vi = (vi，vj)Evj)E， 则称则称vjvj，vjvj为为e ek k的端点的端点， e ek k与与vivi、vjvj是彼此是彼此相关联的相关联的 起终点相同的边称为起终点相同的边称为环环 不与任何边关联的结点称为不与任何边关联的结点称为孤立点孤立点（包括有向向图（包括有向向图) )5 5）邻接：）邻接： 边的相邻边的相邻：e ek k，e el lEE若若e ek k与与e el l至少有一个公共端点，则称至少有一个公共端点，则称e ek k与与e el l是相邻的是相邻的 顶点的相邻顶点的相邻：两个结点为一条边的端点，则称两个结点：两个结点为一条边的端点，则称两个结点互为邻

27、接点互为邻接点， 也称也称边关联于这两个结点边关联于这两个结点，或称两个结点邻接于此边，或称两个结点邻接于此边。6 6）平行边：）平行边： 在无向图中，关联一对顶点的无向边如果多于在无向图中，关联一对顶点的无向边如果多于1 1条，则称这些边为平行边，条，则称这些边为平行边，平行边的条数称为重数平行边的条数称为重数 在有向图中，关联一对顶点的有向边如果多于在有向图中，关联一对顶点的有向边如果多于1 1条，并且这些边的始点与条，并且这些边的始点与终点相同终点相同( (也就是它们的方向相同也就是它们的方向相同) )，则称这些边为平行边，则称这些边为平行边 7 7）多重图和简单图：）多重图和简单图：含

28、平行边的图称为多重图含平行边的图称为多重图 既不含平行边也不含环的图称为既不含平行边也不含环的图称为简单图简单图3 3、结点的度、结点的度 设设G GVE为无向图，为无向图， v V v V，称，称v v作为边的端点次数之和作为边的端点次数之和为为v v的度数，简记为的度数，简记为d dG G(v)(v)即为：结点即为：结点v v 所关联的边的总条数所关联的边的总条数 关于有向图关于有向图D DV E 有：有： v Vv V，称，称v v 作为边的作为边的始点的次数之和始点的次数之和为为v v的出度，记作的出度，记作d d- - (v)(v)， 称称v v作为边的终点的次数之和为作为边的终点的

29、次数之和为v v的入度，记作的入度，记作d d+ + (v)(v)， 称称d d+ +(v) + d(v) + d- -( v)( v)为为 v v的度数，记作的度数，记作d dD D (v)(v) 4 4、结点的度、结点的度 1 1）定义）定义4 4 设设G GVE为无向图，为无向图， v V v V，称，称v v作为边的端点次数之和作为边的端点次数之和为为v v的度数，简记为度记作的度数，简记为度记作d d G G(v)(v)， 简记为简记为d dG G(v)(v)即为：结点即为：结点v v 所关联的边的总条数所关联的边的总条数 关于有向图关于有向图D DV E 有：有： v Vv V，称

30、，称v v 作为边的作为边的始点的次数之和始点的次数之和为为v v的出度，记作的出度，记作d d- - (v)(v)， 称称v v作为边的终点的次数之和为作为边的终点的次数之和为v v的入度，记作的入度，记作d d+ + (v)(v)， 称称d d+ +(v) + d(v) + d- -( v)( v)为为 v v的度数，记作的度数，记作d dD D (v)(v) 2) 2) 称度数为称度数为1 1的顶点为悬挂顶点，与它关联的边称为悬挂边的顶点为悬挂顶点，与它关联的边称为悬挂边5 5、握手定理（欧拉）、握手定理（欧拉）1)1)设设G G为任意无向图为任意无向图,V,Vvv1 1，v v2 2，

31、v vn n,E E = m = m， 则则 d(vd(vi i) ) 2 m ( 2 m (所有结点的度数值和为边数的所有结点的度数值和为边数的2 2倍倍) )2)2)设设D D为任意有向图为任意有向图,V,Vvv1 1，v v2 2，v vn n,|E| = m ,|E| = m ， 则则 d d+ +(v(vi i) ) d d- -(v(vi i) = m) = m 且且d(vd(vi i) )2 m2 m3) 3) 推论推论 任何图任何图( (无向的或有向的无向的或有向的) )中，中，奇度顶点的个数是偶数奇度顶点的个数是偶数4) 4) 结点的度数序列结点的度数序列 (1) (1) 设

32、设G GVE为一个为一个n n阶无向图，阶无向图，V Vvv1 1，v v2 2，v vn n 称称d(vd(v1 1) )，d(vd(v2 2) )， ，d(vd(vn n) ) 为为G G的度数列的度数列 条件：条件：奇度数奇度数的结点个数应该是的结点个数应该是偶数个偶数个 （2 2）序列的可图化：）序列的可图化： d=(d d=(d1 1,d,d2 2, ,d dn n) ) 对一个整数序列对一个整数序列d,d,若存在以若存在以n n个顶点的个顶点的n n阶无向图阶无向图G G，有，有d(vd(vi i)=d)=di i 称该序列是可图化的称该序列是可图化的（3 3）设非负整数列）设非负

33、整数列d d(d1(d1，d2d2，dn)dn)则则d d是可图化的当且仅当是可图化的当且仅当 ddi i = 0 (mod 2) = 0 (mod 2) ( (序列之和必须是偶数序列之和必须是偶数) )（4 4）结论：）结论：n n个结点的个结点的简单图简单图中结点的最大中结点的最大度数（度数（G)G)）应小于）应小于等于等于n-1n-16 6、图的同构、图的同构定义定义: :两个图的各结点之间，如果存在着一一对应关系两个图的各结点之间，如果存在着一一对应关系f f 这种对应关系又保持了这种对应关系又保持了结点间的邻接关系结点间的邻接关系，那么这两个图就是，那么这两个图就是同构的同构的 在有

34、向图的情况下，在有向图的情况下，f f不但应该保持结点间的邻接关系，还应该不但应该保持结点间的邻接关系，还应该保持边的方向保持边的方向注：注：1) 1) 互为互为同构的两个图（必要条件）同构的两个图（必要条件） 有有相同样的阶数相同样的阶数（结点）和（结点）和同样数量的边数同样数量的边数及顶点的及顶点的度数序列度数序列 2) 2)图之间的图之间的同构关系同构关系可看成全体图集合上的二元关系可看成全体图集合上的二元关系同构的图为一个等价类，在同构的图为一个等价类，在同构的意义之下都可以看成是一个图。同构的意义之下都可以看成是一个图。 画出画出4 4阶阶3 3条边的所有非同构的条边的所有非同构的无

35、向简单图无向简单图主要掌握：给出边集主要掌握：给出边集E E，能表示出图，能表示出图 简单图的判断简单图的判断 握手定理的应用握手定理的应用习题类型：习题类型： 习题十四习题十四 3 3、5 5、8 8 7 7、完全图定义、完全图定义 设设G G为为n n阶无向简单图，若阶无向简单图，若G G中每个顶点均与其余的中每个顶点均与其余的n n1 1个顶点相邻，则称个顶点相邻，则称G G为为n n阶无向完全图，简称阶无向完全图，简称n n阶完全图阶完全图，记作记作KnKn(n1)(n1) 设设D D为为n n阶有向简单图，若阶有向简单图，若D D中每个顶点都中每个顶点都邻接到邻接到其余的其余的n n

36、1 1个顶个顶点，又点，又邻接于邻接于其余的其余的n n1 1个顶点，则称个顶点，则称D D是是n n阶阶有向完全图有向完全图完全图的性质：完全图的性质： n n阶无向完全图阶无向完全图G G的边数与结点的关系的边数与结点的关系 m = m = n (n-1)/2n (n-1)/2 n n阶有向完全图阶有向完全图G G的边数与结点的关系的边数与结点的关系 m = m = n (n-1)n (n-1)8 8、通路通路：首尾相接的边的序列首尾相接的边的序列L L称为通路称为通路 2 2、序列中、序列中首尾结点相同首尾结点相同，则称，则称L L为回路为回路 3 3、通路的表示：边的集合表示、通路的表

37、示：边的集合表示 可仅用通路中的可仅用通路中的边序列表示边序列表示：e e1 1e e2 2e ek k 也可仅用通路中所经过的也可仅用通路中所经过的结点的序列表示结点的序列表示：v v1 1v v2 2v v4 4v v1 1v v3 3 4 4、边序列中的、边序列中的各条边全都是互不相同各条边全都是互不相同的通路，称为的通路，称为简单通路简单通路 5 5、序列中的、序列中的每一个结点仅出现一次每一个结点仅出现一次的通路，称为的通路，称为初级通路初级通路 6 6、序列中、序列中首尾结点相同首尾结点相同，则称通路为，则称通路为初级回路或圈初级回路或圈。 7 7、序列中、序列中边的条数边的条数称

38、为它的称为它的长度长度 8 8、关系：有向图中的每一条、关系：有向图中的每一条初级通路初级通路，也都，也都必定是简单通路必定是简单通路。 反之不成立反之不成立 9 9、在、在n n阶图阶图D D中，若从顶点中，若从顶点vivi到到vjvj存在简单通路存在简单通路，则，则vivi到到vjvj一定一定存在长度小于或等于存在长度小于或等于n n1 1的初级通路的初级通路 1010、在一个、在一个n n阶图阶图D D中，若存在中，若存在vivi到自身的到自身的简单回路简单回路，则一定存，则一定存在在vivi到自身到自身长度长度小于或等于小于或等于n n的初级回路（圈）的初级回路（圈） 掌握：初级通路与

39、简单通路的判断，及其关系掌握：初级通路与简单通路的判断，及其关系9 9、图的连通性图的连通性1 1）无向图的连通性无向图的连通性 结点的连通：结点的连通： 设无向图设无向图G GVE， u,v Vu,v V，若，若u u，v v之间之间存在通路则称存在通路则称u,vu,v是连通的是连通的记作记作u uv v， u Vu V，规定，规定u uu u 结点的连通关系是等价关系结点的连通关系是等价关系 若定义：若定义： u uv u，vVvV且且 u u与与v v之间有通路之间有通路 此关系是此关系是自反，对称的，传递的，自反，对称的，传递的，因而是因而是V V上的上的等价关系等价关系2 2）无向图

40、的连通图无向图的连通图 若无向图若无向图G G中中任何两个顶点都是连通的任何两个顶点都是连通的，则称，则称G G为连通图，为连通图， 否则称否则称G G为非连通图或分离图（各子图为为非连通图或分离图（各子图为连通分支连通分支- - 等价类等价类）3 3）结点之间的距离结点之间的距离 设设u u，v v为无向图为无向图G G中任意两个顶点中任意两个顶点, ,若若u uv v，称，称u u，v v之间长度最短之间长度最短的通路为的通路为u u，v v之间的短程线之间的短程线 短程线的长度称为短程线的长度称为u u，v v之间的之间的距离距离，记作，记作 d(ud(u，v)v) 当当u u，v v不

41、连通时，规定不连通时，规定d(ud(u，v)v) 4 4）有向图的连通性有向图的连通性1 1、结点的可达性：设、结点的可达性：设D DVE为一个有向图为一个有向图 vi,vj Vvi,vj V，若，若从从vivi到到vjvj存在通路存在通路, ,则称则称vivi可达可达vj,vj, 记作记作vi vj vi vj 。 规定规定vivi总是可总是可达自身的达自身的，即，即vi vivi vi2 2、结点的相互可达、结点的相互可达 若若vi vj vi vj 且且vj vi vj vi 则称则称vivi与与vjvj是相互可达的，是相互可达的， 记作记作: : vi vi vj vj ( (规定规定

42、vi vi vi vi) )3 3、 结点的可达关系可为结点的可达关系可为V V上的二元关系，但上的二元关系，但不是等价关系不是等价关系4 4、有向图中结点的距离定义：设、有向图中结点的距离定义：设D DVE为有向图为有向图 vi,vj Vvi,vj V，若，若 vi vjvi vj，称，称vivi到到vivi长度最短的通路为长度最短的通路为vivi到到vjvj的短程线的短程线 短程线的长度为短程线的长度为vivi到到vjvj的的距离距离，记作，记作dvidvj 一般地：一般地：dvid vj dvjd vi （可能（可能d d 不存在）不存在） 5 5）设设D DVV，E)E)为一个有向图为

43、一个有向图 若若D D的的作为无向图是连通图作为无向图是连通图，则称，则称D D是弱连通图是弱连通图，简称为，简称为连通图连通图 若若 vi,vj V vi,vj V , vi vj, vi vj与与vj vivj vi至少成立其一至少成立其一，则称，则称D D是是单单向连通图向连通图 若若 vi,vj Vvi,vj V，均有，均有vi vi vj vj，则称，则称D D是是强连通图强连通图 三种图的关系：三种图的关系：强连通图一定是强连通图一定是单向连通图单向连通图，反之不成立，反之不成立 单向连通图一定是单向连通图一定是弱连通图弱连通图反之不成立反之不成立 掌握：对有向图和无向图连通的判断

44、掌握：对有向图和无向图连通的判断 连通关系与可达关系的性质连通关系与可达关系的性质 1010、图的矩阵表示、图的矩阵表示1 1）无向图的关联矩阵无向图的关联矩阵令令m mijij为顶点为顶点v vi i与边与边e ej j的关联次数的关联次数，则称则称(m(mijij) )为为G G的关联矩阵，记作的关联矩阵，记作 M(G)M(G)2 2）关联矩阵的性质）关联矩阵的性质: : 关联矩阵是关联矩阵是n n行（结点数）行（结点数）m m列（边数）列（边数）的矩阵的矩阵 (1(1）M(G)M(G)每列元素之和均为每列元素之和均为2 2，这正说明每条边关联两个顶点，这正说明每条边关联两个顶点( (环所

45、关联的两个环所关联的两个端点重合端点重合) )mij = 2 (j = 1mij = 2 (j = 1，2 2，m)m)(2(2）M(G)M(G)第第i i行元素之和为结点行元素之和为结点vivi的度数，的度数，i i1 1，2 2，n n(3) (3) 所有行的和（即矩阵所有元素之和）等于边数的所有行的和（即矩阵所有元素之和）等于边数的2 2倍。倍。 d(vi)d(vi)mij= 2 mij= 2 2m2m，这个结果满足握手定理，这个结果满足握手定理（4 4）第）第j j列与第列与第k k列相同，当且仅当边列相同，当且仅当边ejej与与ekek是平行边是平行边 (5) (5) 某行某行i i

46、的和为的和为0 0（即（即 mij = 0mij = 0）, ,当且仅当当且仅当vivi是孤立点是孤立点3 3）有向图的有向图的关联矩阵关联矩阵设有向图设有向图D DVE中无环，中无环，V Vvv1 1，v v2 2，v vn n 。 E Eeel l，e e2 2, ,，e em m ，令令 1 v1 vi i为边为边e ej j的起点的起点 m mijij = = 0 v0 vi i为边为边e ej j不关联不关联 1 v1 vi i为边为边e ej j的终点的终点 则称则称(m(mijij) )nxmnxm，为，为D D的关联矩阵，记作的关联矩阵，记作M(DM(D）4 4) )有向图关联

47、矩阵的性质有向图关联矩阵的性质 （1 1） mij= 0mij= 0，j j1 1，2 2，m m，从而，从而mij = 0mij = 0，这说明，这说明M(D)M(D)中所有元中所有元素之和为素之和为0 0 (2) M(D)(2) M(D)中，负中，负1 1的个数等于正的个数等于正1 1的个数，都等于边数的个数，都等于边数m m，这正是有向图握手定，这正是有向图握手定理的内容（入度之和等于出度之和）理的内容（入度之和等于出度之和） （3 3）第）第i i行中，正行中，正1 1的个数等于的个数等于d+(vi)d+(vi)（结点的入度），负（结点的入度），负1 1的个数等于的个数等于d-(vi)

48、d-(vi)（结点的出度）（结点的出度） （4 4）平行边所对应的列相同）平行边所对应的列相同 关联矩阵要求掌握：定义及性质关联矩阵要求掌握：定义及性质5 5）有向图的有向图的邻接矩阵邻接矩阵 设有向图设有向图D DVE，V Vv1v1，v2v2，vnvn，E Ee1e1，e2e2，emem 令：令： aijaij为顶点为顶点vivi邻接到顶点邻接到顶点vjvj边的条数边的条数 称称(aij)nxn(aij)nxn为为D D的邻接矩阵，记作的邻接矩阵，记作A(D)A(D) 邻接矩阵的性质邻接矩阵的性质 每列元素之和为每列元素之和为结点的入度结点的入度，即，即 aijaijd d+ +(vi)(

49、vi)，i i1 1，2 2，n n 所有所有列的和列的和 aij aij d d+ +(vi) (vi) m m ，等于边数，等于边数 每行元素之和为结点的出度每行元素之和为结点的出度，所有行的和也等于边数，所有行的和也等于边数 邻接矩阵中元素邻接矩阵中元素 aij aij 反映了反映了有向图中结点有向图中结点vivi到到vjvj通路长度为通路长度为1 1的的条数条数A(D)A(D)中所有元素之和为中所有元素之和为D D中长度为中长度为1 1的（边）通路总条数的（边）通路总条数。 主对角线的元素值为图中结点主对角线的元素值为图中结点vivi长度为长度为1 1 的的环的条数环的条数 利用利用A

50、(D)A(D)确定出确定出D D中中长度为长度为L L的通路数和回路数的通路数和回路数, ,就需要用到邻接矩就需要用到邻接矩阵的阵的幂次运算幂次运算A A2 2中的元素值中的元素值bijbij是结点是结点vivi到到vjvj长度为长度为2 2 的通路条数的通路条数：A A3 3矩阵中的矩阵中的C Cijij元素值，表示了从到长度恰为元素值，表示了从到长度恰为3 3的通路条数目的通路条数目A A的的L L次幂次幂A AL L(L1)(L1)中元素中元素c cijij为为D D中中vivi到到vjvj长度为长度为L L的通路数，的通路数， 其中其中ciicii为为vivi到自身长度为到自身长度为L

51、 L的回路数的回路数设设B BL LA + AA + A2 2十十+A+AL L (L1) (L1)， 则则BLBL中元素中元素 bijbij为为D D中长度小于或等于中长度小于或等于L L的的通路数通路数， 其中主对角线上元素值为其中主对角线上元素值为D D中长度小于或等于中长度小于或等于L L的回路数的回路数主要掌握：对于给出的图能准确得到其邻接矩阵主要掌握：对于给出的图能准确得到其邻接矩阵 能计算邻接矩阵各次幂能计算邻接矩阵各次幂 能利用邻接矩阵及其各次幂得出图的各结点到另外结点能利用邻接矩阵及其各次幂得出图的各结点到另外结点长度为长度为d d的通路（回路）条数的通路（回路）条数 各个结

52、点的出度及入度各个结点的出度及入度习题：习题：P291 1P291 1、3 3、5 5、8 8、1414、4343、4444、4545、4646、4747 11 11、欧拉图与哈密顿图、欧拉图与哈密顿图1 1）欧拉图）欧拉图定义：给定一个无向图定义：给定一个无向图G G= 。( (a a) )穿程图穿程图G G中的每条边一次且仅一次中的每条边一次且仅一次的通路，定义为该图的通路，定义为该图G G的欧拉通路。的欧拉通路。( (b b) )穿程图穿程图G G中的每条边一次且仅一次的回路，定义为该图中的每条边一次且仅一次的回路，定义为该图G G的欧拉回路。的欧拉回路。( (c c) )具有具有欧拉回

53、路欧拉回路的图，称为的图，称为欧拉图欧拉图 具有具有欧拉通路欧拉通路而无欧拉回路的图称为而无欧拉回路的图称为半欧拉图半欧拉图2 2）性质）性质 每一个欧拉图都必定是个连通无向图每一个欧拉图都必定是个连通无向图连通无向图连通无向图G G中中没有奇度结点没有奇度结点，当且仅当图，当且仅当图G G是个欧拉图是个欧拉图 无向图无向图G G是半欧拉图当且仅当是半欧拉图当且仅当G G是连通的且是连通的且G G中中恰有两个奇度数结点恰有两个奇度数结点3 3）哈密顿图）哈密顿图定义：给定一个无向图定义：给定一个无向图G G= ( (a a) )穿程图穿程图G G中的中的每个结点一次且仅一次的每个结点一次且仅一

54、次的通路，称为该图通路，称为该图G G的哈密顿通路的哈密顿通路(b)(b)穿程图穿程图G G中的中的每个结点一次且仅一次的回路每个结点一次且仅一次的回路，定义为该图，定义为该图G G的哈密顿回路。的哈密顿回路。(c)(c)具有哈密顿回路的图。称为哈密顿图。具有哈密顿通路但不具有哈密顿回具有哈密顿回路的图。称为哈密顿图。具有哈密顿通路但不具有哈密顿回路的图称为半哈密顿图路的图称为半哈密顿图4 4）性质：）性质： 每一个哈密顿图都必定是个连通无向图每一个哈密顿图都必定是个连通无向图 哈密顿通路是一条初级通路哈密顿通路是一条初级通路 哈密顿回路是初级回路哈密顿回路是初级回路要求掌握：定义及其性质要求

55、掌握：定义及其性质1212、树、树1 1）定义：）定义： 连通无回路连通无回路（初级回路或简单回路）的无向图称为无向（初级回路或简单回路）的无向图称为无向树，或简称树。常用树，或简称树。常用T T表示树，平凡图称为平凡树表示树，平凡图称为平凡树 在无向树中，在无向树中，悬挂顶点称为树叶悬挂顶点称为树叶，度数大于或等于，度数大于或等于2 2的顶点称为的顶点称为分支结点分支结点 树的等价定义树的等价定义 (2) G (2) G中任中任意两个顶点之间存在惟一的路径意两个顶点之间存在惟一的路径 (3) G (3) G中中无回路且无回路且 m = n - 1 m = n - 1 (4) G (4) G是

56、是连通的且连通的且 m = n - 1 m = n - 12 2）树的性质）树的性质 对于给定的无向图对于给定的无向图树是树是边数最小的连通图边数最小的连通图（mn-1mn-1mn-1则有回路）则有回路） 结点的度：结点的度： d(vi) = 2 m =d(vi) = 2 m =2(n-1)2(n-1) 设设T T是是n n阶非平凡的无向树，则阶非平凡的无向树，则T T中至少有两片树叶中至少有两片树叶 主要掌握：主要掌握：树的定义树的定义 树的性质树的性质 习题类型：习题类型： p318 2 p318 2、4 4、1313五、代数结构部分五、代数结构部分1 1、二元运算的一般性质、二元运算的一

57、般性质对以下的各个性质要有四个实际的运算作为模型来理解对以下的各个性质要有四个实际的运算作为模型来理解）交换律：）交换律： 如果对于任意的如果对于任意的x x，ySyS都有都有 x xy = yy = yx x 则称运算在则称运算在S S上是可交换的，或者说运算在上是可交换的，或者说运算在S S上适合交换律。上适合交换律。2 2）结合律结合律 设为设为S S上的二元运算，如果对于任意的上的二元运算，如果对于任意的x x，y y，zSzS都有都有: : (x(xy) y) z = xz = x(y (y z)z) 则称运算则称运算 在在S S上是可结合的，或者说运算上是可结合的，或者说运算 在在

58、S S上适合结合律上适合结合律3 3）等幂律等幂律 设设 为为S S上的二元运算，如果对于任意的上的二元运算，如果对于任意的xSxS都有都有 x xx xx x 则称该运算则称该运算 适合幂等律适合幂等律如果如果S S中的某些中的某些x x满足满足x xx=xx=x，则称，则称x x为运算的幂等元为运算的幂等元如果如果S S上的二元运算适合幂等律，则上的二元运算适合幂等律，则S S中的所有元素都是幂等元中的所有元素都是幂等元 4 4）分配律分配律（一种运算对另一种运算而言）（一种运算对另一种运算而言） 设设 和和 o o 是是S S上的两个二元运算，上的两个二元运算， 如果对任意的如果对任意的

59、x x，y y，zSzS有有 x x(y o z)(y o z)(x(xy) o(xy) o(xz) (z) (左分配律左分配律) ) (y o z) (y o z) x = (yx = (yx) o(zx) o(zx) (x) (右分配律右分配律) ) 则称运算对则称运算对 o o 是可分配的，也称对是可分配的，也称对 o o 适合分配律适合分配律5 5）吸收律吸收律 （一种运算对另一种运算而言）（一种运算对另一种运算而言） 设设 o o 和是和是S S上两个可交换的二元运算，上两个可交换的二元运算，如果对于任意的如果对于任意的x x，ySyS都有都有 x x(x o y)(x o y)x

60、x x o(x x o(xy )=xy )=x 则称则称o o和满足吸收律和满足吸收律 对以上的各个公理要有四个实际的运算作为模型来对以上的各个公理要有四个实际的运算作为模型来6 6）单位元（幺元）单位元（幺元）对任何对任何xSxS都有都有: : e el l x = xx = x ( (或或 x x e er r = x = x ) ) 则称则称e el l( (或或e er r) )是是S S中关于运算的一个中关于运算的一个左单位元左单位元( (或或右单位元右单位元) )若若eSeS关于运算既是左单位元又是右单位元，关于运算既是左单位元又是右单位元， 则称则称e e为为S S上关于运算的单