《CH图的基本概念》由会员分享，可在线阅读，更多相关《CH图的基本概念（76页珍藏版）》请在金锄头文库上搜索。
1、本章内容本章内容14.1 14.1 图图14.2 14.2 通路与回路通路与回路14.3 14.3 图的连通性图的连通性14.4 14.4 图的矩阵表示图的矩阵表示14.5 14.5 图的运算图的运算基本要求基本要求作业作业114.1 14.1 图的基本概念图的基本概念q图的定义图的定义q图的一些概念和规定图的一些概念和规定q简单图和多重图简单图和多重图q顶点的度数与握手定理顶点的度数与握手定理q图的同构图的同构q完全图与正则图完全图与正则图q子图与补图子图与补图2无序积与多重集合无序积与多重集合无序积与多重集合无序积与多重集合 q设设A A，B B为任意的两个集合，称为任意的两个集合，称 a
2、, ,b | |aAbBAbB为为A A与与B B的的无序积无序积，记作，记作A&BA&B。可将无序积中的无序对可将无序积中的无序对 a, ,b 记为记为( (a, ,b) )，并且允许并且允许ab。无论无论a,ba,b是否相等，均有是否相等，均有( (a, ,b) )( (b, ,a) )，因而因而A&BA&BB&AB&A。q元素可以重复出现的集合称为元素可以重复出现的集合称为多重集合多重集合或者或者多重集多重集，某元，某元素重复出现的次数称为该元素的素重复出现的次数称为该元素的重复度重复度。例如例如 在多重集合在多重集合 a, ,a, ,b, ,b, ,b, ,c, ,d 中，中， a,
3、,b, ,c, ,d的重复度分别为的重复度分别为2,3,1,12,3,1,1。 3定义定义14.114.1 一个一个无向图无向图是一个有序的二元组是一个有序的二元组 ,E,记作记作G G，其中其中（1 1）VV称为称为顶点集顶点集，其元素称为，其元素称为顶点顶点或或结点结点。（2 2）E E称为称为边集边集，它是，它是无序积无序积V&VV&V的多重子集，其元素称为的多重子集，其元素称为无向无向边边，简称，简称边边。定义定义14.214.2 一个一个有向图有向图是一个有序的二元组是一个有序的二元组 E，记作记作D D，其中其中（1 1）VV称为称为顶点集顶点集，其元素称为，其元素称为顶点顶点或或
4、结点结点。（2 2）E E为为边集边集，它是，它是笛卡儿积笛卡儿积VVVV的多重子集，其元素称为的多重子集，其元素称为有向有向边边，简称，简称边边。无向图和有向图无向图和有向图无向图和有向图无向图和有向图说明说明q可以用图形表示图，即用小圆圈（或实心点）表示顶可以用图形表示图，即用小圆圈（或实心点）表示顶点，用顶点之间的连线表示无向边，用有方向的连线点，用顶点之间的连线表示无向边，用有方向的连线表示有向边。表示有向边。 4例例例例14.114.114.114.1例例14.114.1 (1) (1) 给定无向图给定无向图G G，其中其中 V Vvv1 1,v,v2 2,v,v3 3,v,v4 4
5、,v,v5 5 ，E=(vE=(v1 1,v,v1 1),(v),(v1 1,v,v2 2),(v),(v2 2,v,v3 3),(v),(v2 2,v,v3 3),(v),(v2 2,v,v5 5),(v),(v1 1,v,v5 5),(v),(v4 4,v,v5 5). ). (2) (2) 给定有向图给定有向图D=D=，其中其中 V Va,b,c,da,b,c,d，E E,。 画出画出G G与与D D的图形。的图形。5图的一些概念和规定图的一些概念和规定图的一些概念和规定图的一些概念和规定qG G表示无向图，但有时用表示无向图，但有时用G G泛指图泛指图( (无向的或有向的无向的或有向的
6、) )。qD D只能表示有向图。只能表示有向图。qV(G)V(G)，E(G)E(G)分别表示分别表示G G的的顶点集顶点集和和边集边集。q若若| |V(G)|V(G)|n n，则称则称G G为为n n阶图阶图。q若若| |V(G)|V(G)|与与| |E(G)|E(G)|均为有限数，则称均为有限数，则称G G为为有限图有限图。 q若边集若边集E(G)E(G)，则称则称G G为为零图零图，此时，又若，此时，又若G G为为n n阶图，则称阶图，则称G G为为n n阶零图阶零图，记作，记作N Nn n，特别地，称特别地，称N N1 1为为平凡图平凡图。 q在图的定义中规定顶点集在图的定义中规定顶点集
7、V V为非空集，但在图的运算中可能产为非空集，但在图的运算中可能产生顶点集为空集的运算结果，为此规定生顶点集为空集的运算结果，为此规定顶点集为空集的图顶点集为空集的图为为空空图图，并将空图记为，并将空图记为。 6标定图与非标定图、基图标定图与非标定图、基图 q将图的集合定义转化成图形表示之后，常用将图的集合定义转化成图形表示之后，常用e ek k表示表示无向边无向边( (v vi i,v,vj j) )（或或有向边有向边 ），），并称并称顶点或边用字母标定顶点或边用字母标定的图的图为为标定图标定图，否则称为，否则称为非标定图非标定图。q将有向图各将有向图各有向边均改成无向边后的无向图有向边均改
8、成无向边后的无向图称为原来图的称为原来图的基图基图。q易知标定图与非标定图是可以相互转化的，任何无向图易知标定图与非标定图是可以相互转化的，任何无向图G G的各边均加上箭头就可以得到以的各边均加上箭头就可以得到以G G为基图的有向图。为基图的有向图。 7关联与关联次数、环、孤立点关联与关联次数、环、孤立点 q设设G G为无向图，为无向图，ek( (vi, ,vj)E)E，称称vi, ,vj为为ek的端点的端点，ek与与vi或或ek与与vj是彼此相是彼此相关联关联的。的。若若vivj，则称则称ek与与vi或或ek与与vj的的关联次数为关联次数为1 1。若若vivj，则称则称ek与与vi的的关联次
9、数为关联次数为2 2，并称，并称ek为为环环。任意的任意的vlVV，若若vlvi且且vlvj，则称则称ek与与vl的的关联次数为关联次数为0 0。 q设设D D为有向图，为有向图，ek EE，称称vi, ,vj为为ek的的端点。端点。若若vivj，则称则称ek为为D D中的中的环环。q无论在无向图中还是在有向图中，无边关联的顶点均称为无论在无向图中还是在有向图中，无边关联的顶点均称为孤立孤立点点。 8相邻与邻接相邻与邻接 q设无向图设无向图G GVE，vi，vjVV，ek，elEE。若若 etEE，使得使得et( (vi，vj) )，则称则称vi与与vj是是相邻的相邻的。若若ek与与el至少有
10、一个公共端点至少有一个公共端点，则称，则称ek与与el是是相邻的相邻的。 q设有向图设有向图D DVE，vi，vjVV，ek，elEE。若若 etEE，使得使得et ，则称则称vi为为et的的始点始点，vj为为et的的终终点点，并称，并称vi邻接到邻接到vj，vj邻接于邻接于vi。若若ek的终点为的终点为el的始点，则称的始点，则称ek与与el相邻相邻。9邻域邻域q设无向图设无向图G ， vV，称称 u| |uV(u, ,v)Euv 为为v的的邻域邻域，记做，记做NG( (v) )。称称NG G( (v)v 为为v的的闭邻域闭邻域，记做，记做NG(v)(v)。称称 e| |eEe与与v相关联相
11、关联 为为v的的关联集关联集，记做，记做IG( (v) )。q设有向图设有向图D ， vV，称称 u| |uVV EEuv 为为v的的后继元集后继元集，记做，记做+ +D( (v)v)。称称 u| |uVV EEuv 为为v的的先驱元集先驱元集，记做，记做- -D( (v)v)。称称+ +D D( (v)- -D D( (v) )为为v的的邻域邻域，记做，记做ND( (v) )。称称ND( (v)v 为为v的的闭邻域闭邻域，记做，记做ND( (v) )。10举例举例举例举例N NG G( (v1 1) ) + +D( (d ) ) v2 2，v5 5 NG(v1) v1 1，v2 2，v5 5
12、 I IG G( (v1 1) ) e1 1，e2 2，e3 3 c - -D(D(d ) ) a，c N ND D( (d ) ) a，c N ND D( (d ) ) a，c，d 11简单图与多重图简单图与多重图 定义定义14.314.3 在无向图中，关联一对顶点的无向边如果在无向图中，关联一对顶点的无向边如果多于多于1 1条条，则称这些边为则称这些边为平行边平行边，平行边的条数称为，平行边的条数称为重数重数。在有向图中，关联一对顶点的有向边如果在有向图中，关联一对顶点的有向边如果多于多于1 1条条，并且这些，并且这些边的边的始点和终点相同始点和终点相同( (也就是它们的方向相同也就是它们
13、的方向相同) )，则称这些边，则称这些边为为平行边平行边。含平行边的图称为含平行边的图称为多重图多重图。既不含平行边也不含环的图既不含平行边也不含环的图称为称为简单图简单图。例如：例如：在图在图14.114.1中，中，( (a)a)中中e e5 5与与e e6 6是平行边，是平行边，( (b)b)中中e e2 2与与e e3 3是平行边，但是平行边，但e e6 6与与e e7 7不是平行边。不是平行边。( (a)a)和和( (b)b)两个图都不是简单图。两个图都不是简单图。12顶点的度数顶点的度数定义定义14.414.4 设设G G为一无向图，为一无向图， vVV，称称v作为边的端点作为边的端
14、点次数之和为次数之和为v的度数的度数，简称为，简称为度度，记做，记做 dG( (v) )。在不发生混淆时，简记为在不发生混淆时，简记为d( (v) )。设设D DVE为有向图，为有向图， vVV，称称v作为边的始点次数之和为作为边的始点次数之和为v的出度的出度，记做，记做d+ +D( (v) )，简记作简记作d+ +( (v) )。称称v作为边的终点次数之和为作为边的终点次数之和为v的入度的入度，记做，记做d -D( (v) )，简记作简记作d- -( (v) )。称称d+ +( (v)+)+d- -( (v) )为为v v的的度数度数，记做，记做d( (v) )。13图的度数的相关概念图的度
15、数的相关概念q在无向图在无向图G G中，中，最大度最大度(G)G)maxmaxd( (v)|)|vV(G)V(G)最小度最小度(G)(G)mind(mind(v)|)|vV(G) V(G) q在有向图在有向图D D中，中，最大出度最大出度+ +( (D)D)maxmaxd+ +( (v)|)|vV(D)V(D)最小出度最小出度+ +(D)(D)minmind+ +( (v)|)|vV(D)V(D)最大入度最大入度- -(D)(D)maxmaxd- -( (v)|)|vV(D)V(D)最小入度最小入度- -(D)(D)minmind- -( (v)|)|vV(D)V(D)q称度数为称度数为1 1
16、的顶点为的顶点为悬挂顶点悬挂顶点，与它关联的边称为，与它关联的边称为悬挂边悬挂边。度为偶数度为偶数( (奇数奇数) )的顶点称为的顶点称为偶度偶度( (奇度奇度) )顶点顶点。 14图的度数举例图的度数举例d( (v1 1) )4(4(注意，环提供注意，环提供2 2度度) )，4 4，1 1，v4 4是悬挂顶点，是悬挂顶点，e7 7是悬挂边。是悬挂边。d+ +( (a) )4 4，d- -( (a) )1 1( (环环e1 1提供出度提供出度1 1，提供入度，提供入度1)1)，d( (a) )4+14+15 5。5 5，3 3，+ +4 (4 (在在a点达到点达到) )+ +0(0(在在b点达
17、到点达到) )- -3(3(在在b点达到点达到) )- -1(1(在在a和和c点达到点达到) ) 15握手定理握手定理定理定理14.114.1 设设G G为任意无向图，为任意无向图，V V v1 1, ,v2 2,vn ，|E|E|m，则则说明说明任何无向图中，各顶点度数之和等于边数的两倍。任何无向图中，各顶点度数之和等于边数的两倍。证明证明G G中每条边中每条边( (包括环包括环) )均有两个端点，均有两个端点，所以在计算所以在计算G G中各顶点度数之和时，中各顶点度数之和时，每条边均提供每条边均提供2 2度，当然，度，当然，m条边，共提供条边，共提供2 2m度。度。 定理定理14.2 14
18、.2 设设D D为任意有向图，为任意有向图，V V v1 1, ,v2 2,vn ，|E|E|m，则则 16握手定理的推论握手定理的推论推论推论任何图任何图( (无向的或有向的无向的或有向的) )中，奇度顶点的个数是偶数。中，奇度顶点的个数是偶数。 证明证明设设G GVE为任意一图，令为任意一图，令V V1 1 v| |vVVd( (v) )为奇数为奇数 V V2 2 v| |vVVd( (v) )为偶数为偶数 则则V V1 1VV2 2V V，V V1 1VV2 2 ，由握手定理可知由握手定理可知 由于由于2 2m和和，所以，所以为偶数为偶数，但因但因V V1 1中顶点度数为奇数，中顶点度数
19、为奇数， 所以所以| |V V1 1| |必为偶数。必为偶数。17问题研究问题研究问题：问题：在一个部门的在一个部门的2525个人中间，由于意见不同，是否可能每个个人中间，由于意见不同，是否可能每个人恰好与其他人恰好与其他5 5个人意见一致？个人意见一致？解答：解答：不可能不可能。考虑一个图，其中顶点代表人，如果两个人意见。考虑一个图，其中顶点代表人，如果两个人意见相同，可用边连接，所以每个顶点都是奇数度。存在奇数个度相同，可用边连接，所以每个顶点都是奇数度。存在奇数个度数为奇数的图，这是不可能的。数为奇数的图，这是不可能的。说明：说明：(1)(1)很多离散问题可以用图模型求解。很多离散问题可
20、以用图模型求解。(2)(2)为了建立一个图模型，需要决定顶点和边分别代表什么。为了建立一个图模型，需要决定顶点和边分别代表什么。(3)(3)在一个图模型中，边经常代表两个顶点之间的关系。在一个图模型中，边经常代表两个顶点之间的关系。18度数列度数列设设G G为一个为一个n阶无向图，阶无向图，V V v1 1, ,v2 2,vn ，称称d( (v1 1) )，d( (v2 2) )，d( (vn n) )为为G G的的度数列度数列。对于顶点标定的无向图，它的度数列是唯一的。对于顶点标定的无向图，它的度数列是唯一的。反之，对于给定的非负整数列反之，对于给定的非负整数列d d1 1, ,d2 2,d
21、n ，若存在若存在V V v1 1, ,v2 2,vn 为顶点集的为顶点集的n阶无向图阶无向图G G，使得使得d( (vi) )di，则称则称d是是可图化的可图化的。特别地，若所得图是简单图，则称特别地，若所得图是简单图，则称d是是可简单图化的可简单图化的。类似地，设类似地，设D D为一个为一个n n阶有向图，阶有向图，V V v1 1, ,v2 2,vn ，称称d( (v1 1) )，d( (v2 2) )，d( (vn) )为为D D的的度数列度数列，另外称，另外称d+ +( (v1 1) )，d+ +( (v2 2) )，d+ +( (vn) )与与d- -( (v1 1) )，d- -
22、( (v2 2) )，d- -( (vn) )分别为分别为D D的的出度列出度列和和入度列入度列。19度数列举例度数列举例按顶点的标定顺序，度数列为按顶点的标定顺序，度数列为4,4,2,1,34,4,2,1,3。按字母顺序，度数列，出度列，入按字母顺序，度数列，出度列，入度列分别为度列分别为5,3,3,35,3,3,34,0,2,14,0,2,11,3,1,21,3,1,220可图化的充要条件可图化的充要条件定理定理14.314.3 设非负整数列设非负整数列d( (d1 1，d2 2，dn) )，则则d d是可图化的当是可图化的当且仅当且仅当 证明证明必要性。必要性。由握手定理显然得证。由握手
23、定理显然得证。充分性。充分性。由已知条件可知，由已知条件可知，d中有偶数个奇数度点。中有偶数个奇数度点。奇数度点两两之间连一边，剩余度用环来实现。奇数度点两两之间连一边，剩余度用环来实现。533121定理定理14.314.3的证明的证明由握手定理可知必然性显然。由握手定理可知必然性显然。下面证明充分性。下面证明充分性。由已知条件可知，由已知条件可知，d d中有中有2 2k(0kn/2)k(0kn/2)个奇数，个奇数，不妨设它们为不妨设它们为d d1 1，d d2 2，d dk k，d dk+1k+1，d dk+2k+2，d d2k2k。可用多种方法做出可用多种方法做出n n阶无向图阶无向图G
24、G，V Vvv1 1,v,v2 2,v,vn n 。比如边集如下产生：在顶点比如边集如下产生：在顶点v vr r与与v vr+kr+k之间连边，之间连边，r r1,2,k1,2,k。若若d di i为偶数，令为偶数，令d d i id di i，若若d di i为奇数，令为奇数，令d d i id di i-1-1，得得d d (d(d 1 1，d d 2 2，d d n n) )，则则d d i i均为偶数。均为偶数。再在再在v vi i处做出处做出d d i i/2/2条环条环, ,i i1,n1,n，将所得各边集合在一起组成将所得各边集合在一起组成E E，则则G G的度数列为的度数列为d
25、 d。其实，其实，d di i为偶数时，为偶数时，d(vd(vi i) )2d2d i i/2/22d2di i/2/2d di i，当当d di i为奇数时，为奇数时，d(vd(vi i) )1+2d1+2d i i/2/21+d1+d i i1+d1+di i-1-1d di i，这就证明了这就证明了d d是可图化的。是可图化的。 22可图化举例可图化举例由定理由定理14.314.3立即可知，立即可知，(3,3,2,1)(3,3,2,1)，(3,2,2,1,1)(3,2,2,1,1)等是不可图化的，等是不可图化的，(3,3,2,2)(3,3,2,2)，(3,2,2,2,1)(3,2,2,2
26、,1)等是可图化的。等是可图化的。 23定理定理14.414.4定理定理14.414.4 设设G G为任意为任意n阶无向简单图，则阶无向简单图，则(G)G)n-1-1。 证明证明因为因为G G既无平行边也无环，既无平行边也无环，所以所以G G中任何顶点中任何顶点v至多与其余的至多与其余的n-1-1个顶点均相邻，个顶点均相邻，于是于是d( (v)n-1-1，由于由于v v的任意性，所以的任意性，所以(G)G)n-1-1。例例14.214.2 判断下列各非负整数列哪些是可图化的？哪些是可简判断下列各非负整数列哪些是可图化的？哪些是可简单图化的？单图化的？(1) (5,5,4,4,2,1)(1) (
27、5,5,4,4,2,1)不可图化。不可图化。(2) (5,4,3,2,2)(2) (5,4,3,2,2)可图化，不可简单图化。若它可简单图化，可图化，不可简单图化。若它可简单图化，设所得图为设所得图为G G，则则(G)G)max5,4,3,2,2max5,4,3,2,25 5，这与定理这与定理14.414.4矛盾。矛盾。 24例例14.214.2(3) (3,3,3,1)(3) (3,3,3,1)可图化，不可简单图化。假设该序列可以简单图化，可图化，不可简单图化。假设该序列可以简单图化，设设G GVE以该序列为度数列。以该序列为度数列。不妨设不妨设V Vvv1 1,v,v2 2,v,v3 3,
28、v,v4 4 且且 d(vd(v1 1) )d(vd(v2 2) )d(vd(v3 3) )3,d(v3,d(v4 4) )1 1，由于由于d(vd(v4 4) )1 1，因而因而v v4 4只能与只能与v v1 1，v v2 2，v v3 3之一相邻，之一相邻，于是于是v v1 1，v v2 2，v v3 3不可能都是不可能都是3 3度顶点，这是矛盾的，度顶点，这是矛盾的，因而因而(3)(3)中序列也不可简单图化。中序列也不可简单图化。(4) (4) (d d1 1,d,d2 2,d,dn n) )，d d1 1dd2 2ddn n1 1 且且 为偶数。为偶数。 可图化，不可简单图化。可图化
29、，不可简单图化。25例例14.214.2(5) (4,4,3,3,2,2) (5) (4,4,3,3,2,2) 可简单图化。下图中两个可简单图化。下图中两个6 6阶无向简单图都以阶无向简单图都以(5)(5)中序列为度中序列为度数列。数列。26图的同构图的同构定义定义14.514.5 设设G G1 1V ，G G2 2V 为两个无向图，为两个无向图，若存在双射函数若存在双射函数f f：V V1 1VV2 2，对于对于vi, ,vjVV1 1，( (vi, ,vj)E)E1 1当且仅当当且仅当( (f(f(vi),f(),f(vj)E)E2 2， 并且并且 ( (vi, ,vj) )与与( (f(
30、f(vi),f(),f(vj)的重数相同，的重数相同，则称则称G G1 1与与G G2 2是同构的是同构的，记做，记做G G1 1G G2 2。说明说明(1) (1) 类似地，可以定义两个有向图的同构。类似地，可以定义两个有向图的同构。(2) (2) 图的同构关系看成全体图集合上的二元关系。图的同构关系看成全体图集合上的二元关系。(3) (3) 图的同构关系是等价关系。图的同构关系是等价关系。(4) (4) 在图同构的意义下，图的数学定义与图形表示在图同构的意义下，图的数学定义与图形表示 是一一对应的。是一一对应的。27图的同构举例图的同构举例彼得森彼得森( (Petersen) )图图28图
31、同构的必要条件：图同构的必要条件：q节点数目相等节点数目相等q边数相等边数相等q度数相同的节点数目相等度数相同的节点数目相等29完全图完全图定义定义14.614.6 设设G G为为n阶无向简单图，若阶无向简单图，若G G中中每个顶点均与其余的每个顶点均与其余的n-1-1个顶点相邻个顶点相邻，则称，则称G G为为n阶无向完全图阶无向完全图，简称，简称n阶完全图阶完全图，记做，记做K Kn( (n1)1)。 设设D D为为n阶有向简单图，若阶有向简单图，若D D中每个顶点都邻接到其余的中每个顶点都邻接到其余的n-1-1个顶个顶点，又邻接于其余的点，又邻接于其余的n-1-1个顶点，则称个顶点，则称D
32、 D是是n阶有向完全图阶有向完全图。设设D D为为n阶有向简单图，若阶有向简单图，若D D的基图为的基图为n阶无向完全图阶无向完全图K Kn，则称则称D D是是n阶竞赛图阶竞赛图。30完全图举例完全图举例n阶无向完全图的边数为：阶无向完全图的边数为： n( (n-1)/2-1)/2n阶有向完全图的边数为：阶有向完全图的边数为： n( (n-1)-1)n阶竞赛图的边数为：阶竞赛图的边数为：n( (n-1)/2-1)/2K5 53 3阶有向完全图阶有向完全图4 4阶竞赛图阶竞赛图31正则图正则图定义定义14.714.7 设设G G为为n阶无向简单图，若阶无向简单图，若vV(G)V(G)，均有均有d
33、( (v) )k，则称则称G G为为k- -正则图正则图。 举例举例n阶零图是阶零图是0-0-正则图正则图n阶无向完全图是阶无向完全图是( (n-1)-1)-正则图正则图彼得森图是彼得森图是3-3-正则图正则图说明说明n阶阶k- -正则图中，边数正则图中，边数mkn/2/2。当当k为奇数时，为奇数时，n必为偶数。必为偶数。32子图子图定义定义14.814.8 设设G ，G 为两个图为两个图( (同为无向图或同为无向图或同为有向图同为有向图) )，若，若V V且且E E，则称则称G G 是是G G的的子图子图，G为为G 的的母图母图，记作，记作G G。若若V V或或E E，则称则称G 为为G的的
34、真子图真子图。若若V V，则称则称G 为为G的的生成子图生成子图。 设设G 为一图，为一图，V1 1 V且且V1 1，称以称以V1 1为顶点集，以为顶点集，以G中中两个端点都在两个端点都在V1 1中的边中的边组成边集组成边集E1 1的图为的图为G的的V1 1导出的子导出的子图图，记作，记作G V1 1 。设设E1 1 E且且E1 1，称以称以E1 1为边集，以为边集，以E1 1中边关联的顶点为顶中边关联的顶点为顶点集点集V1 1的图的图为为G的的E1 1导出的子图导出的子图，记作，记作G E1 1 。33导出子图举例导出子图举例在上图中，设在上图中，设G G为为(1)(1)中图所表示，中图所表
35、示，取取V V1 1a,b,ca,b,c，则则V V1 1的导出子图的导出子图GVGV1 1 为为(2)(2)中图所示。中图所示。取取E E1 1ee1 1,e,e3 3 ，则则E E1 1的导出子图的导出子图GEGE1 1 为为(3)(3)中图所示。中图所示。34定义定义14.914.9定义定义14.914.9 设设G 为为n阶无向简单图，阶无向简单图，以以V为顶点集为顶点集，以所，以所有有使使G成为完全图成为完全图Kn的添加边组成的集合的添加边组成的集合为边集的图，称为为边集的图，称为G的的补图补图，记作，记作G。若图若图GG，则称为则称为G是是自补图自补图。(1)(1)为自补图为自补图(
36、2)(2)和和(3)(3)互为补图互为补图35定义定义14.1014.10定义定义14.1014.10 设设G 为无向图。为无向图。(1)(1)设设eE，用用G- -e表示从表示从G G中去掉边中去掉边e，称为称为删除删除e。设设E E，用用G- -E 表示从表示从G中删除中删除E 中所有的边，称为中所有的边，称为删除删除E 。(2)(2)设设vV，用用G- -v表示从表示从G中去掉中去掉v及所关联的一切边，称为及所关联的一切边，称为删除顶删除顶点点v。设设V V，用用G- -V 表示从表示从G中删除中删除V 中所有顶点，称为中所有顶点，称为删除删除V 。(3)(3)设边设边e( (u, ,v
37、)E，用用G e表示从表示从G中删除中删除e后，将后，将e的两个端点的两个端点u, ,v用一个新的顶点用一个新的顶点w( (或用或用u或或v充当充当w) )代替，使代替，使w关联除关联除e外外u, ,v关联关联的所有边，称为的所有边，称为边边e的收缩的收缩。(4)(4)设设u, ,vV( (u, ,v可能相邻，也可能不相邻可能相邻，也可能不相邻) )，用用G(u, ,v) )( (或或G+(+(u, ,v) ) )表示在表示在u, ,v之间加一条边之间加一条边( (u, ,v) )，称为称为加新边加新边。说明说明在收缩边和加新边过程中可能产生环和平行边。在收缩边和加新边过程中可能产生环和平行边
38、。36举例举例GGe5G e1, , e4 Gv5G v4, , v5 G e53714.2 14.2 通路与回路通路与回路定定义义14.1114.11 设设G为为无无向向标标定定图图，G中中顶顶点点与与边边的的交交替替序序列列vi0ej1vi1ej2vi2ejivil称称为为vi0到到vil的的通通路路，其其中中，vir-1, ,vir为为ejr的的端端点点，r 1 1，2 2，l，vi0，vil分分别别称称为为的的始始点点与与终终点点，中中边边的的条条数称为它的数称为它的长度长度。若若vi0vil，则称通路为，则称通路为回路回路。若若的的所有边各异所有边各异，则称，则称为为简单通路简单通路
39、，又若又若vi0vil，则称，则称为为简单回路简单回路。若若的的所所有有顶顶点点( (除除vi0 0与与vij可可能能相相同同外外) )各各异异，所所有有边边也也各各异异，则则称称为为初级通路初级通路或或路径路径，又若又若vi0 0vil，则称，则称为为初级回路初级回路或或圈圈。将长度为奇数的圈称为将长度为奇数的圈称为奇圈奇圈，长度为偶数的圈称为，长度为偶数的圈称为偶圈偶圈。 38关于通路与回路的说明关于通路与回路的说明q在初级通路与初级回路的定义中，仍将初级回路看成初级通在初级通路与初级回路的定义中，仍将初级回路看成初级通路路( (路径路径) )的特殊情况，只是在应用中初级通路的特殊情况，只
40、是在应用中初级通路( (路径路径) )都是始都是始点与终点不相同的，点与终点不相同的，长为长为1 1的圈只能由环生成的圈只能由环生成，长为长为2 2的圈只的圈只能由平行边生成能由平行边生成，因而在，因而在简单无向图中，圈的长度至少为简单无向图中，圈的长度至少为?。q若若中有中有边重复边重复出现，则称出现，则称为为复杂通路复杂通路，又若又若vi0 0v vil，则称则称为为复杂回路复杂回路。 q在有向图中在有向图中，通路、回路及分类的定义与无向图中非常相似，通路、回路及分类的定义与无向图中非常相似，只是只是要注意有向边方向的一致性要注意有向边方向的一致性。 q在以上的定义中，将回路定义成通路的特
41、殊情况，即在以上的定义中，将回路定义成通路的特殊情况，即回路也回路也是通路是通路，又，又初级通路初级通路( (回路回路) )是简单通路是简单通路( (回路回路) )，但反之不真。，但反之不真。39通路和回路的简单表示法通路和回路的简单表示法(1)(1)只用边的序列表示通路只用边的序列表示通路( (回路回路) )。定义。定义14.1114.11中的中的可以表示可以表示成成ej1 1 , ,ej2 2 , , , ,ejl。(2)(2)在简单图中也可以只用顶点序列表示通路在简单图中也可以只用顶点序列表示通路( (回路回路) )。定义中。定义中的的也可以表示成也可以表示成vi0 0 , ,vi2 2
42、 , , , ,vil。(3)(3)为了写出非标定图中的通路为了写出非标定图中的通路( (回路回路) )，可以先将非标定图标，可以先将非标定图标成标定图，再写出通路与回路。成标定图，再写出通路与回路。(4)(4)在非简单标定图中，当只用顶点序列表示不出某些通路在非简单标定图中，当只用顶点序列表示不出某些通路( (回回路路) )时，可在顶点序列中加入一些边时，可在顶点序列中加入一些边( (这些边是平行边或环这些边是平行边或环) )，可称这种表示法为，可称这种表示法为混合表示法混合表示法。 40定理定理14.514.5定定理理14.514.5 在在n阶阶图图G中中，若若从从顶顶点点vi到到vj（v
43、ivj）存存在在通通路路，则则从从vi到到vj存在长度小于或等于存在长度小于或等于n-1-1的通路。的通路。 证明证明设设v0 0e1 1v1 1e2 2elvl( (v0 0vi , ,vlvj) )为为G中一条长度为中一条长度为l的通路，的通路，若若ln-1-1，则则满足要求，满足要求，否则必有否则必有l+1+1n，即即上的顶点数大于上的顶点数大于G中的顶点数，中的顶点数，于是必存在于是必存在k, ,s,0,0k sl，使得使得 vsvk, ,即在即在上存在上存在vs到自身的回路到自身的回路Csk, ,在在上删除上删除C Csk上的一切边及除上的一切边及除vs外的一切顶点，外的一切顶点，得
44、得 v0 0e1 1v1 1e2 2vkes+1+1 elvl , , 仍为仍为vi到到vj的通路，的通路，且长度至少比且长度至少比减少减少1 1。若若 还不满足要求，则重复上述过程，由于还不满足要求，则重复上述过程，由于G是有限图，经过是有限图，经过有限步后，必得到有限步后，必得到vi到到vj长度小于或等于长度小于或等于n-1-1的通路。的通路。 41定理定理14.614.6推论推论 在在n阶图阶图G中，若从顶点中，若从顶点vi到到vj（vivj）存在通路，则存在通路，则vi到到vj一定存在长度小于或等于一定存在长度小于或等于n-1-1的初级通路（路径）。的初级通路（路径）。 定理定理14.
45、614.6 在一个在一个n阶图阶图G中，若存在中，若存在vi 到自身的回路，则一定到自身的回路，则一定存在存在vi 到自身长度小于或等于到自身长度小于或等于n的回路。的回路。 推论推论 在一个在一个n阶图阶图G中，若存在中，若存在vi 到自身的简单回路，则一定到自身的简单回路，则一定存在存在vi 到自身长度小于或等于到自身长度小于或等于n的初级回路。的初级回路。42例例14.414.4例例14.414.4 无向完全图无向完全图Kn( (n3)3)中有几种非同构的圈？中有几种非同构的圈？解答解答长度相同的圈都是同构的，长度相同的圈都是同构的，因而只有长度不同的圈才是非同构的，因而只有长度不同的圈
46、才是非同构的，易知易知Kn( (n3)3)中含长度为中含长度为3 3，4 4，n的圈，的圈，所以所以Kn( (n3)3)中有中有n-2-2种非同构的圈。种非同构的圈。 43例例14.514.5例例14.514.5 无向完全图无向完全图K3 3的顶点依次标定为的顶点依次标定为a, ,b, ,c。在定义意义下在定义意义下K3 3中有多少个不同的圈？中有多少个不同的圈？解答解答在同构意义下，在同构意义下，K3 3中只有一个长度为中只有一个长度为3 3的圈。的圈。但在定义意义下，不同起点但在定义意义下，不同起点( (终点终点) )的圈是不同的，的圈是不同的，顶点间排列顺序不同的圈也看成是不同的，顶点间
47、排列顺序不同的圈也看成是不同的，因而因而K3 3中有中有6 6个不同的长为个不同的长为3 3的圈：的圈：abca ，acba ，bacb ，bcab ，cabc ，cbac如果只考虑起点如果只考虑起点( (终点终点) )的差异，的差异，而不考虑顺时针逆时针的差异，应有而不考虑顺时针逆时针的差异，应有3 3种不同的圈，种不同的圈，当然它们都是同构的，画出图来只有一个。当然它们都是同构的，画出图来只有一个。 4414.3 14.3 图的连通性图的连通性q无向图的连通性无向图的连通性q无向图中顶点之间的短程线及距离无向图中顶点之间的短程线及距离q无向图的连通程度：点割集、割点、边割集、割边、连通度无
48、向图的连通程度：点割集、割点、边割集、割边、连通度q有向图的连通性及判别方法有向图的连通性及判别方法q扩大路径法与极大路径扩大路径法与极大路径q二部图及其判别方法二部图及其判别方法 45无向图的连通性无向图的连通性定定义义14.1214.12 设设无无向向图图G ， u, ,vV，若若u, ,v之之间间存存在在通通路，则称路，则称u, ,v是是连通的连通的，记作，记作uv。 vV，规定规定vv。 无向图中顶点之间的连通关系无向图中顶点之间的连通关系 （u, ,v）| | u, ,vVV且且u与与v之间有通路之间有通路 是自反的、对称的、传递的，因而是自反的、对称的、传递的，因而是是V V上的等
49、价关系上的等价关系。46连通图与连通分支连通图与连通分支定义定义14.1314.13 若无向图若无向图G是平凡图或是平凡图或G中任何两个顶点都是连通中任何两个顶点都是连通的，则称的，则称G为为连通图连通图，否则称，否则称G是是非连通图非连通图或或分离图分离图。说明：说明：完全图完全图Kn( (n1)1)都是连通图都是连通图零图零图Nn( (n2)2)都是分离图。都是分离图。 定义定义14.1414.14 设无向图设无向图G ，V关于顶点之间的连通关系关于顶点之间的连通关系的的商集商集V/ / V1 1, ,V2 2,Vk ，Vi为等价类，称导出子图为等价类，称导出子图G Vi ( (i1,2,
50、1,2,k) )为为G的的连通分支连通分支，连通分支数连通分支数k常记为常记为p( (G) )。 说明说明若若G为连通图，则为连通图，则p( (G) )1 1。若若G为非连通图，则为非连通图，则p( (G)2)2。在所有的在所有的n阶无向图中，阶无向图中，n阶零图是连通分支最多的，阶零图是连通分支最多的，p( (Nn) )n。 47无向图中顶点之间的短程线及距离无向图中顶点之间的短程线及距离 定义定义14.1514.15 设设u, ,v为无向图为无向图G G中任意两个顶点，若中任意两个顶点，若uv，称称u, ,v之间之间长度最短的通路长度最短的通路为为u, ,v之间的之间的短程线短程线，短程线
51、的长度称为，短程线的长度称为u, ,v之间之间的的距离距离，记作，记作d( (u, ,v) )。当当u, ,v不连通时，规定不连通时，规定d( (u, ,v) )。 距离有以下性质：距离有以下性质：(1)(1)d( (u, ,v)0)0，uv时，等号成立。时，等号成立。(2)(2)具有对称性，具有对称性，d( (u, ,v) )d( (v, ,u) )。(3)(3)满足三角不等式：满足三角不等式： u, ,v, ,wV( (G) )，则则d( (u, ,v)+)+d( (v, ,w)d( (u, ,w) )说明：说明：在完全图在完全图Kn( (n2)2)中，任何两个顶点之间的距离都是中，任何两
52、个顶点之间的距离都是1 1。在在n阶零图阶零图Nn( (n2)2)中，任何两个顶点之间的距离都为中，任何两个顶点之间的距离都为。48如何定义连通度如何定义连通度q问题问题：如何定量地比较无向图的连通性的强与弱？：如何定量地比较无向图的连通性的强与弱？q点连通度点连通度：为了破坏连通性，至少需要删除多少个顶点？：为了破坏连通性，至少需要删除多少个顶点？q边连通度边连通度：为了破坏连通性，至少需要删除多少条边？：为了破坏连通性，至少需要删除多少条边？q“破坏连通性破坏连通性”是指是指“变得更加不连通变得更加不连通” ” 。49无向图的点无向图的点割割集集定义定义14.1614.16 设无向图设无向
53、图G ，若存在若存在V V，且且V ，使得使得p( (G- -V )p( (G) )，而对于任意的而对于任意的V V ，均有均有p( (G- -V ) )p( (G) )，则称则称V 是是G的的点割集点割集。若若V 是单元集，即是单元集，即V v ，则称则称v为为割点割点。 v2 2, ,v4 4,v3 3,v5 5 都是点割集都是点割集v3 3, ,v5 5都是割点都是割点v1 1与与v6 6不在任何割集中。不在任何割集中。 实际上，点割集是若删去实际上，点割集是若删去它们就会使图不连通的它们就会使图不连通的顶点的集合，而割点是顶点的集合，而割点是若删去此一顶点就会使若删去此一顶点就会使图不
54、连通的顶点。图不连通的顶点。50无向图的边割集无向图的边割集无向图的边割集无向图的边割集定义定义14.1714.17设无向图设无向图G ，若存在若存在E E，且且E ，使使得得p( (G- -E )p( (G) )，而对于任意的而对于任意的E E ，均有均有p( (G- -E ) )p( (G) )，则称则称E 是是G的的边割集边割集，或简称为，或简称为割集割集。若若E 是单元集，即是单元集，即E ee，则称则称e为为割边割边或或桥桥。 e6 6,e,e5 5,e2 2, ,e3 3,e1 1, ,e2 2,e3 3, ,e4 4,e1 1, ,e4 4,e1 1, ,e3 3,e2 2, ,
55、e4 4 都是割集，都是割集，e6 6, ,e5 5是桥。是桥。 实际上，边割集是若删去实际上，边割集是若删去它们就会使图不连通的边它们就会使图不连通的边的集合，而割边是若删去的集合，而割边是若删去此一边就会使图不连通的此一边就会使图不连通的边。边。51点连通度点连通度定义定义14.1814.18设设G为无向连通图且为非完全图，则称为无向连通图且为非完全图，则称 ( (G) )minmin| |V | | |V 为为G的点割集的点割集 为为G的的点连通度点连通度，简称，简称连通度连通度。说明说明 连通度是为了产生一个不连通图需要删去的点的连通度是为了产生一个不连通图需要删去的点的最少最少数目。
56、数目。规定完全图规定完全图Kn( (n1)1)的点连通度为的点连通度为n-1-1，规定规定非连通图的点连通度为非连通图的点连通度为0 0，若若 ( (G)k，则称则称G G是是k- -连通图连通图，k为非负整数。为非负整数。说明说明 ( (G) )有时简记为有时简记为。上例中图的点连通度为上例中图的点连通度为1 1，此图为，此图为1-1-连通图。连通图。K5 5的点连通度的点连通度K4 4，所以所以K5 5是是1-1-连通图，连通图，2-2-连通图，连通图，3-3-连通图，连通图，4-4-连通图。连通图。若若G是是k- -连通图（连通图（k11）则在则在G中删除任何中删除任何k-1-1个顶点后
57、，所得图个顶点后，所得图一定还是连通的。一定还是连通的。 52边连通度边连通度定义定义14.1914.19 设设G是无向连通图，称是无向连通图，称 (G ) )minmin| |E | | | E 是是G G的边割集的边割集 为为G的的边连通度边连通度。规定非连通图的边连通度为规定非连通图的边连通度为0 0。若若(G)r，则称则称G是是r 边边- -连通图连通图。 说明说明 (G) )也可以简记为也可以简记为。若若G是是 r 边边- -连通图，则在连通图，则在G G中任意删除中任意删除r-1-1条边后，所得图依然是条边后，所得图依然是连通的。连通的。完全图完全图Kn的边连通度为的边连通度为n-
58、1-1，因而因而Kn是是r边边- -连通图，连通图，00rn-1-1。 平凡图平凡图G G 由于由于E E 则则0 0图图14.814.8中图的边连通度中图的边连通度1 1，它只能是它只能是1 1边边- -连通图。连通图。53例例14.614.6求所示各图的点连通度，边连通度，并指出它们各是几连通图及求所示各图的点连通度，边连通度，并指出它们各是几连通图及几边连通图。最后将它们按点连通程度及边连通程度排序。几边连通图。最后将它们按点连通程度及边连通程度排序。K4 4K3 3K2 2K1 1K=1 =21 =2K2 2K0 0K0 054例例14.614.6的解答的解答设第设第i个图的点连通度为
59、个图的点连通度为Ki，边连通度为边连通度为i，I I1,2,81,2,8。容易看出，容易看出，K1 11 14 4，K2 22 23 3，K3 33 32 2，K4 44 41 1， K5 5=1 =1 5 5=2=2，K6 66 62 2，K7 77 70 0，K8 88 80 0。(1)(1)是是k- -连通图，连通图，k边边- -连通图，连通图，k1,2,3,41,2,3,4。(2)(2)是是k- -连通图，连通图，k边边- -连通图，连通图，k1,2,31,2,3。(3)(3)是是k- -连通图，连通图，k边边- -连通图，连通图，k1,21,2。(4)(4)是是1-1-连通图，连通图
60、，1 1边边- -连通图。连通图。(5)(5)是是1-1-连通图，连通图，k边边- -连通图，连通图，k1,21,2。(6)(6)是是k- -连通图，连通图，k边边- -连通图，连通图，k1,21,2。(7)(7)是是0-0-连通图，连通图，0 0边边- -连通图。连通图。(8)(8)是是0-0-连通图，连通图，0 0边边- -连通图。连通图。点连通程度为点连通程度为(1)(2)(3)(1)(2)(3)(6)(4)(6)(4)(5)(7)(5)(7)(8)(8)。边连通程度为边连通程度为(1)(2)(3)(1)(2)(3)(5)(5)(6)(4)(7)(6)(4)(7)(8)(8)。55定理定
61、理14.714.7（惠特尼）（惠特尼）定理定理14.714.7 对于任何无向图对于任何无向图G，有有 ( (G)()(G)()(G)()(证明证明) )例例14.714.7 ( (1)1)给出一些无向简单图，使得给出一些无向简单图，使得 。 (2) (2)给出一些无向简单图，使得给出一些无向简单图，使得 。解答解答 (1) (1) n阶无向完全图阶无向完全图Kn和和n阶零图阶零图Nn都满足要求。都满足要求。(2)(2)在两个在两个Kn( (n4)4)之间放置一个顶点之间放置一个顶点v，使使v与两个与两个Kn中的每一个中的每一个的任意两个不同的顶点相邻，所得简单图满足要求。的任意两个不同的顶点相
62、邻，所得简单图满足要求。因为这样的图中有一个割点，所以点连通度为因为这样的图中有一个割点，所以点连通度为1 1，又因为无桥，而有两条边组成的边割集，所以边连通度为又因为无桥，而有两条边组成的边割集，所以边连通度为2 2，当当n4 4时，时，3 3，当当n55时，时，4 4。56q证明：如果图证明：如果图G G是不连通图或者是平凡图，则有是不连通图或者是平凡图，则有 ( (G)=G)= (G)=0(G)=0 (G)(G)；q任给一个连通图任给一个连通图G G，若，若 (G)=k(G)=k，则存在边割，则存在边割EE，| E| = | E| = k k。现取。现取EE中每一条边的一个端点构成顶点集
63、中每一条边的一个端点构成顶点集VV，即，即V=u | (u, v)EV=u | (u, v)E且且v v VV。显然。显然|V| |V| k k 。而。而G GVV是不连通的，即是不连通的，即VV是是G G的一个顶点割。所以的一个顶点割。所以 (G) (G) |V| |V| (G)(G)。q若若G G是非平凡图，则因为每一个顶点所关联的边构成一个边是非平凡图，则因为每一个顶点所关联的边构成一个边割，故有割，故有 (G)(G) (G)(G)。q综上所述，有综上所述，有 (G) (G) (G)(G) (G)(G)。57有向图的连通性有向图的连通性定定义义14.2014.20 设设D 为为一一个个有
64、有向向图图。vi, ,vjV，若若从从vi到到vj存存在通路，则称在通路，则称vi可达可达vj，记作记作vivj，规定规定vi总是可达自身的，即总是可达自身的，即vivi。若若vivj且且vjvi，则称则称vi与与vj是是相互可达相互可达的，记作的，记作vi vj。规定规定vivi。 说明说明 与与都是都是V V上的二元关系，并且不难看出上的二元关系，并且不难看出是是V上的等上的等价关系。价关系。 定义定义14.2114.21 设设D 为有向图，为有向图，vi, ,vjVV，若若vivj，称称vi到到vj长度最短的通路长度最短的通路为为vi到到vj的的短程线短程线，短程线的长度为短程线的长度为
65、vi到到vj的距离，记作的距离，记作d 。说明说明 与无向图中顶点与无向图中顶点vi与与vj之间的距离之间的距离d( (vi, ,vj) )相比，相比，d 除除无对称性外，具有无对称性外，具有d( (vi, ,vj) )所具有的一切性质。所具有的一切性质。 58连通图连通图定义定义14.2214.22 设设D 为一个有向图。若为一个有向图。若D的基图是连通图，则称的基图是连通图，则称D是是弱连通图弱连通图，简称为，简称为连通图连通图。若若vi, ,vjV，vivj与与vjvi至少成立其一，则称至少成立其一，则称D是是单向连通图单向连通图。若均有若均有vi vj，则称则称D是是强连通图强连通图。
66、说明说明 强连通图一定是单向连通图，强连通图一定是单向连通图，单向连通图一定是弱连通图。单向连通图一定是弱连通图。 强连通图强连通图单向连通图单向连通图弱连通图弱连通图59强连通图与单向连通图的判定定理强连通图与单向连通图的判定定理定定理理14.814.8 设设有有向向图图D ，V v1 1, ,v2 2,vn 。D是是强强连连通通图图当且仅当当且仅当D中存在经过每个顶点至少一次的回路。中存在经过每个顶点至少一次的回路。 证明证明 充分性充分性显然。显然。下面证明下面证明必要性必要性。由由D的强连通性可知，的强连通性可知，vivi+1+1，i1,2,1,2,n-1-1。设设i为为vi到到vi+
67、1+1的通路。的通路。又因为又因为vnv1 1，设设n为为vn到到v1 1的通路，则的通路，则1 1,2 2,n-1-1,n所所围成的回路经过围成的回路经过D中每个顶点至少一次。中每个顶点至少一次。定理定理14.914.9 设设D是是n阶有向图，阶有向图，D是单向连通图当且仅当是单向连通图当且仅当D中存在经中存在经过每个顶点至少一次的通路。过每个顶点至少一次的通路。 证明证明略。略。问题问题 设有向图设有向图D是单向连通图，但不是强连通图，问在是单向连通图，但不是强连通图，问在D中至少中至少加几条边所得图加几条边所得图D 就能成为强连通图？就能成为强连通图？60扩大路径法扩大路径法 q设设G
68、为为n阶无向图，阶无向图，E，设设l为为G G中一条路径，中一条路径，若此路径的始点或终点与通路外的顶点相邻，就将它们扩到若此路径的始点或终点与通路外的顶点相邻，就将它们扩到通路中来通路中来。继续这一过程，直到最后得到的通路的两个端点不与通路外继续这一过程，直到最后得到的通路的两个端点不与通路外的顶点相邻为止。的顶点相邻为止。设最后得到的路径为设最后得到的路径为l+ +k( (长度为长度为l的路径扩大成了长度为的路径扩大成了长度为l+ +k的路径的路径) )，称，称l+ +k为为“极大路径极大路径”，称使用此种方法证明问题的方法为称使用此种方法证明问题的方法为“扩大路径法扩大路径法”。q有向图
69、中可以类似地讨论，只须注意，在每步扩大中保持有有向图中可以类似地讨论，只须注意，在每步扩大中保持有向边方向的一致性。向边方向的一致性。61关于极大路径的说明关于极大路径的说明q由某条路经扩大出的极大路径不唯一。由某条路经扩大出的极大路径不唯一。q极大路径不一定是图中最长的路径。极大路径不一定是图中最长的路径。62例例14.814.8例例14.814.8 设设G为为n（n44）阶无向简单图，阶无向简单图，(G)3)3。证明证明G中存在长度大于或等于中存在长度大于或等于4 4的圈。的圈。 证明证明 不妨设不妨设G是连通图，否则，因为是连通图，否则，因为G的各连通分支的最小度也的各连通分支的最小度也
70、都大于或等于都大于或等于3 3，因而可对它的某个连通分支进行讨论。，因而可对它的某个连通分支进行讨论。设设u, ,v为为G中任意两个顶点，由中任意两个顶点，由G是连通图，因而是连通图，因而u, ,v之间存在通之间存在通路，由定理路，由定理14.514.5的推论可知，的推论可知，u, ,v之间存在路径，用之间存在路径，用“扩大路扩大路径法径法”扩大这条路径，设最后得到的扩大这条路径，设最后得到的“极大路径极大路径”为为lv0 0v1 1vl，易知易知l33。若若v0 0与与vl相邻，则相邻，则l(v0 0, ,vl) )为长度大于或等于为长度大于或等于4 4的圈。的圈。否则，由于否则，由于d(
71、(v0 0)()(G)3)3，因而因而v0 0除与除与l上的上的v1 1相邻外，还相邻外，还存在存在l上的顶点上的顶点vk( (k1)1)和和vt( (kt l ) )与与v0 0相邻，则相邻，则v0 0v1 1vkvtv0 0为一个圈且长度大于或等于为一个圈且长度大于或等于4 4，见图。，见图。 63二部图二部图定定义义14.2314.23 设设G 为为一一个个无无向向图图，若若能能将将V分分成成V1 1和和V2 2( (V1 1V2 2V, ,V1 1V2 2) )，使使得得G中中的的每每条条边边的的两两个个端端点点都都是是一一个个属属于于V1 1，另另一一个个属属于于V2 2，则则称称G
72、为为二二部部图图（或或称称二二分分图图，偶图偶图等），称等），称V1 1和和V2 2为为互补顶点子集互补顶点子集。常将二部图常将二部图G记为记为 。若若G是是简简单单二二部部图图，V1 1中中每每个个顶顶点点均均与与V2 2中中所所有有顶顶点点相相邻邻，则称则称G为为完全二部图完全二部图，记为，记为Kr, ,s，其中其中r| |V1 1| |，s| |V2 2| |。 说明说明n阶零图为二部图。阶零图为二部图。 64二部图举例二部图举例K6的子图的子图K6的子图的子图K3,3K2,3K3,3K2,365二部图的判定定理二部图的判定定理定理定理14.1014.10 一个无向图一个无向图G 是二部
73、图当且仅当是二部图当且仅当G中无奇数长度的回路。中无奇数长度的回路。证明证明必要性必要性。q设图设图G G是二部图是二部图, ,令令C Cv v0 0,v,v1 1,v,v2 2,v,vk k,v,v0 0是是G G的一条回路，其长度为的一条回路，其长度为k+1k+1。q不失一般性，假设不失一般性，假设v v0 0VV1 1，由二部图的定义知，由二部图的定义知，v v1 1VV2 2，v v2 2VV1 1。由此可。由此可知，知，v v2i2iVV1 1且且v v2i+12i+1VV2 2。q又因为又因为v v0 0VV1 1，所以，所以v vk kVV2 2，因而，因而k k为奇数，故为奇数
74、，故C C的长度为偶数。的长度为偶数。66二部图的判定定理二部图的判定定理充分性充分性。不妨设不妨设G为连通图，否则可对每个连通分支进行讨论。为连通图，否则可对每个连通分支进行讨论。设设v0 0为为G中任意一个顶点，令中任意一个顶点，令V1 1 v| |vV( (G)d( (v0 0, ,v) )为偶数为偶数 V2 2 v| |vV( (G)d( (v0 0, ,v) )为奇数为奇数 易知，易知，V1 1, ,V2 2, ,V1 1V2 2，V1 1V2 2V( (G) )。下面只要证明下面只要证明V1 1中任意两顶点不相邻中任意两顶点不相邻, ,V2 2中任意两点也不相邻。中任意两点也不相邻
75、。若存在若存在vi, ,vjV1 1相邻，令相邻，令( (vi, ,vj) )e，设设v0 0到到vi, ,vj的短程线分别为的短程线分别为i,j，则它们的长度则它们的长度d( (v0 0, ,vi),),d( (v0 0, ,vj) )都是偶数，都是偶数，于是于是ije中一定含奇圈，这与已知条件矛盾。中一定含奇圈，这与已知条件矛盾。类似可证，类似可证，V2 2中也不存在相邻的顶点，于是中也不存在相邻的顶点，于是G为二部图。为二部图。6714.4 14.4 图的矩阵表示图的矩阵表示定义定义14.2414.24 设无向图设无向图G ，V v1 1, ,v2 2,vn ，E e1 1, ,e2 2
76、,em ，令令mij为顶点为顶点vi与边与边ej的关联次数，则称的关联次数，则称( (mij) )nm为为G的的关联矩阵关联矩阵，记作，记作M( (G) )。68有向图的关联矩阵有向图的关联矩阵定义定义14.2514.25 设有向图设有向图D 中无环，中无环，V v1 1, ,v2 2,vn ，E e1 1, ,e2 2,em ，令令 则称则称( (mij) )nm为为D的的关联矩阵关联矩阵，记作，记作M( (D) )。69有向图的邻接矩阵有向图的邻接矩阵定义定义14.2614.26 设有向图设有向图D ，V v1 1, ,v2 2,vn ，E e1 1, ,e2 2,，em ，令令aij(1
77、)(1)为顶点为顶点vi邻接到顶点邻接到顶点vj边的条数，称边的条数，称( (aij(1)(1) )nn为为D D的的邻接矩阵邻接矩阵，记作，记作A( (D) )，或简记为或简记为A。70有向图的可达矩阵有向图的可达矩阵定义定义14.2714.27 设设D 为有向图。为有向图。V v1 1, ,v2 2,vn ，令令 pij1 1 vi 可达可达 vj0 0 否则否则称称( (pij) )nn为为D的的可达矩阵可达矩阵，记作，记作P( (D) )，简记为简记为P。 7114.5 14.5 图的运算图的运算定义定义14.2814.28 设设G1 1 ，G2 2 为两个图。为两个图。若若V1 1V
78、2 2，则称则称G1 1与与G2 2是不交的是不交的。若若E1 1E2 2，则称则称G1 1与与G2 2是是边不交的边不交的或或边不重的边不重的。 说明：说明：不交的图，必然是边不交的，但反之不真。不交的图，必然是边不交的，但反之不真。72图的运算图的运算定义定义14.2914.29 设设G1 1 ，G2 2 为不含孤立点的两个图为不含孤立点的两个图（它们同为无向图或同为有向图）。（它们同为无向图或同为有向图）。(1)(1)称以称以E1 1E2 2为边集，以为边集，以E1 1E2 2中边关联的顶点组成的集合为顶中边关联的顶点组成的集合为顶点集的图为点集的图为G1 1与与G2 2的的并图并图，记
79、作，记作G1 1G2 2。(2)(2)称以称以E1 1- -E2 2为边集，以为边集，以E1 1- -E2 2中边关联的顶点组成的集合为顶中边关联的顶点组成的集合为顶点集的图为点集的图为G1 1与与G2 2的的差图差图，记作，记作G1 1- -G2 2。 (3)(3)称以称以E1 1E2 2为边集，以为边集，以E1 1E2 2中边关联的顶点组成的集合为顶中边关联的顶点组成的集合为顶点集的图为点集的图为G1 1与与G2 2的的交图交图，记作，记作G1 1G2 2。 (4)(4)称以称以E1 1E2 2为边集（为集合之间的对称差运算），以为边集（为集合之间的对称差运算），以E1 1E2 2中边关联
80、的顶点组成的集合为顶点集的图为中边关联的顶点组成的集合为顶点集的图为G1 1与与G2 2的的环和环和，记作记作G1 1G2 2。 73定义定义14.2914.29的说明的说明(1)(1)若若G1 1G2 2，则则G1 1G2 2G1 1G2 2G1 1( (G2 2) )G1 1- -G2 2G2 2- -G1 1G1 1G2 2这就是在图的定义中给出空图概念的原因。这就是在图的定义中给出空图概念的原因。 (2)(2)当当G1 1与与G2 2边不重时，边不重时，G1 1G2 2G1 1- -G2 2G1 1G2 2- -G1 1G2 2G1 1G2 2G1 1G2 2 (3)(3)图之间环和的
81、定义也可以用并、交、差给出，即图之间环和的定义也可以用并、交、差给出，即G1 1G2 2( (G1 1G2 2)-()-(G1 1G2 2) )74基本要求基本要求q理解与图的定义有关的诸多概念，以及它们之间的相互关系。理解与图的定义有关的诸多概念，以及它们之间的相互关系。q深刻理解握手定理及其推论的内容，并能熟练地应用它们。深刻理解握手定理及其推论的内容，并能熟练地应用它们。q深刻理解图同构、简单图、完全图、正则图、子图、补图、二深刻理解图同构、简单图、完全图、正则图、子图、补图、二部图等概念及其它们的性质和相互关系，并能熟练地应用这些部图等概念及其它们的性质和相互关系，并能熟练地应用这些性
82、质和关系。性质和关系。q深刻理解通路与回路的定义、相互关系及其分类，掌握通路与深刻理解通路与回路的定义、相互关系及其分类，掌握通路与回路的各种不同的表示方法。回路的各种不同的表示方法。q理解无向图的点连通度、边连通度等概念及其之间的关系，并理解无向图的点连通度、边连通度等概念及其之间的关系，并能熟练地求出给定的较为简单的图的点连通度与边连通度。能熟练地求出给定的较为简单的图的点连通度与边连通度。q理解有向图连通性的概念及其分类，掌握判断有向连通图类型理解有向图连通性的概念及其分类，掌握判断有向连通图类型的方法。的方法。75作业作业习题十四习题十四6 6、1010、1919、2020、2121、2929、3030、3232、3333、494976
