《第14章图的基本概念》由会员分享，可在线阅读，更多相关《第14章图的基本概念（57页珍藏版）》请在金锄头文库上搜索。
1、CHAPTER CHAPTER FourteenFourteen7/25/2024 6:54 AM Discrete Math. , Chen Chen1离散数学离散数学Discrete MathematicsDiscrete Mathematics CHAPTER CHAPTER FourteenFourteen7/25/2024 6:54 AM Discrete Math. , Chen Chen2第十四章第十四章 图的基本概念图的基本概念11.1 图图11.2 通路与回路通路与回路11.3 图的矩阵表示图的矩阵表示11.4 图的运算图的运算CHAPTER CHAPTER Fourteen
2、Fourteen7/25/2024 6:54 AM Discrete Math. , Chen Chen311.1 图图无向图与有向图无向图与有向图顶点的度数顶点的度数握手定理握手定理图的同构图的同构简单图简单图完全图完全图子图子图补图补图 CHAPTER CHAPTER FourteenFourteen7/25/2024 6:54 AM Discrete Math. , Chen Chen4无序对与多重集合无序对与多重集合无序对与多重集合无序对与多重集合无序对无序对: 2个元素构成的集合个元素构成的集合, 记作记作(a,b)无序积无序积: A B=(x,y) | x A y B例如例如 A=
3、a,b,c, B=1,2 A B=B A=(a,1), (b,1), (c,1), (a,2), (b,2), (c,2) A A=(a,a), (a,b), (a,c), (b,b), (b,c), (c,c) B B=(1,1), (1,2), (2,2)多重集合多重集合: 元素可以重复出现的集合元素可以重复出现的集合重复度重复度: 元素在多重集合中出现的次数元素在多重集合中出现的次数例如例如 S=a,b,b,c,c,c, a,b,c 的重复度依次为的重复度依次为1,2,3CHAPTER CHAPTER FourteenFourteen7/25/2024 6:54 AM Discrete
4、Math. , Chen Chen5无向图无向图定义定义11.1 无向图无向图G=为一个有序的二元组为一个有序的二元组,其中其中 V称为称为顶点集顶点集, 其元素称为其元素称为顶点顶点或或结点结点; E是是V V的的多多重重子子集集, 称称为为边边集集, 其其元元素素称称为为无无向向边边，简简称称边边. 有时用有时用V(G)和和E(G)分别表示分别表示V和和E.图形表示：图形表示：用小圆圈（或实心点）表示顶点，用顶点间的连线表用小圆圈（或实心点）表示顶点，用顶点间的连线表示无向边，用有方向的连线表示有向边。示无向边，用有方向的连线表示有向边。 将图的集合定义转化成图形表示后，常用将图的集合定义
5、转化成图形表示后，常用ek表示无向边表示无向边(vi,vj)(或或有向边有向边)，并称顶点或边用字母标定的图为，并称顶点或边用字母标定的图为标定图标定图，否则称，否则称为为非标定图非标定图 .定义定义11.2 有向图有向图D=, 其中其中 V称为顶点集称为顶点集, 其元素称为其元素称为顶点顶点或或结点结点; E是是V V的多重子集的多重子集, 称为称为边集边集, 其元素称为其元素称为有向边有向边，简称，简称边边. 有时用有时用V(D)和和E(D)分别表示分别表示V和和E .CHAPTER CHAPTER FourteenFourteen7/25/2024 6:54 AM Discrete Ma
6、th. , Chen Chen6有向图有向图有限图有限图: |V(G)|,|E(G)|均为有限数的图均为有限数的图. 例例11.1(2) D=如右下图所示如右下图所示, E= a, a , a, b , a, b , a, d , 其中其中 V=a, b, c, d , d, c , c, d , c, b .例例11.1(1) G=如图所示如图所示, E=(v1,v1), (v1,v2), (v2,v3), (v2,v3), 其中其中 V=v1, v2, ,v5 (v2,v5), (v1,v5), (v4,v5).平凡图平凡图: 1 阶零图阶零图.零图零图: E=的图的图. n 阶图阶图:
7、n个顶点的图个顶点的图.用用|V(G)|,|E(G)|分别表示分别表示G的的顶点数顶点数和和边数边数.CHAPTER CHAPTER FourteenFourteen7/25/2024 6:54 AM Discrete Math. , Chen Chen7顶点和边的关联与相邻顶点和边的关联与相邻设设无无向向图图G=, ek=(vi,vj) E, 称称vi, vj为为ek的的端端点点, ek与与vi ( vj)关关联联. 若若vi = vj, 则称则称ek为为环环. 无边关联的顶点称作无边关联的顶点称作孤立点孤立点.若若vi vj, 则称则称ek与与vi ( vj)的的关联次数为关联次数为1;若
8、若vi = vj, 则称则称ek与与vi 的的关联次数为关联次数为2; 若若vi不是边不是边e的端点的端点, 则称则称e与与vi 的的关联次数为关联次数为0. 设设vi,vj V, ek,el E, 若若(vi,vj) E, 则称则称vi,vj相邻相邻;若若ek,el有一个公共端点有一个公共端点, 则称则称ek,el相邻相邻.对有向图有类似定义对有向图有类似定义.设设ek= vi,vj 是是有有向向图图的的一一条条边边, 又又称称vi是是ek的的始始点点, vj是是ek的的终终点点, vi邻接到邻接到vj, vj邻接于邻接于viCHAPTER CHAPTER FourteenFourteen7
9、/25/2024 6:54 AM Discrete Math. , Chen Chen8邻域和关联集邻域和关联集设无向图设无向图G, v V(G) v的邻域的邻域 N(v)=u|u V(G) (u,v) E(G) u vv的闭邻域的闭邻域 v的邻域的邻域 v的先驱元集的先驱元集 v的后继元集的后继元集 =u|u V(D) E(G) u v=u|u V(D) E(G) u v设有向图设有向图D, v V(D) v的关联集的关联集 I(v)=e|e E(G) e与与v关联关联= N(v) vv的闭邻域的闭邻域CHAPTER CHAPTER FourteenFourteen7/25/2024 6:5
10、4 AM Discrete Math. , Chen Chen9简单图简单图定定义义11.3 在在无无向向图图中中, 关关联联同同一一对对顶顶点点的的2条条或或2条条以以上上的的边边, 称称为为平行边平行边, 平行边的条数称为平行边的条数称为重数重数.在在有有向向图图中中, 具具有有相相同同始始点点和和终终点点的的2条条或或2条条以以上上的的边边称称为为有有向平行边向平行边, 简称简称平行边平行边, 平行边的条数称为平行边的条数称为重数重数.含平行边的图称为含平行边的图称为多重图多重图既无平行边也无环的图称为既无平行边也无环的图称为简单图简单图例例11.1(续续)CHAPTER CHAPTER
11、 FourteenFourteen7/25/2024 6:54 AM Discrete Math. , Chen Chen10顶点的度数顶点的度数定义定义11.4(1)设设G=为无向图为无向图, v V,v的的度度数数(度度) d(v): v作作为为边边的的端端点点次次数数之之和和 悬挂顶点悬挂顶点: 度数为度数为1的顶点的顶点悬挂边悬挂边: 与悬挂顶点关联的边与悬挂顶点关联的边G的最大度的最大度 (G)=maxd(v)| v VG的最小度的最小度 (G)=mind(v)| v V例如例如 右图右图 d(v5)=3, d(v2)=4, d(v1)=4, (G)=4, (G)=1, v4是悬挂顶
12、点是悬挂顶点, e7是悬挂边是悬挂边, e1是环是环CHAPTER CHAPTER FourteenFourteen7/25/2024 6:54 AM Discrete Math. , Chen Chen11顶点的度数顶点的度数(续续)定义定义11.4(2)设设D=为有向图为有向图, v V,v的出度的出度d+(v): v作为边的始点次数之和作为边的始点次数之和v的入度的入度d (v): v作为边的终点次数之和作为边的终点次数之和v的度数的度数(度度) d(v): v作为边的端点次数之和作为边的端点次数之和 d(v)= d+(v)+ d (v)D的最大出度的最大出度 +(D), 最小出度最小出
13、度 +(D) 最大入度最大入度 (D), 最小入度最小入度 (D) 最大度最大度 (D), 最小度最小度 (D) 例如例如右图右图 d+(a)=4, d (a)=1, d(a)=5, d+(b)=0, d (b)=3, d(b)=3, +=4, +=0, =3, =1, =5, =3CHAPTER CHAPTER FourteenFourteen7/25/2024 6:54 AM Discrete Math. , Chen Chen12握手定理握手定理定理定理11.1设设G=为任意无向图为任意无向图, V=v1,v2,vn, |E|=m, 则则 推论推论 任何图任何图(无向图和有向图无向图和有
14、向图)都有偶数个奇度顶点都有偶数个奇度顶点.证证 图中每条边图中每条边(包括环包括环)均有两个端点均有两个端点, 在计算各顶点度数之和时在计算各顶点度数之和时, 每条边均提供每条边均提供2度度, m条边共提供条边共提供2m度度.定理定理11.2设设D=为任意有向图为任意有向图, V=v1,v2,vn, |E|=m, 则则 证证 设设G=为任意图，令为任意图，令 V1=v | v V d(v)为奇数为奇数, V2=v | v V d(v)为偶数为偶数则则V1 V2=V, V1V2=，由握手定理可知，由握手定理可知 CHAPTER CHAPTER FourteenFourteen7/25/2024
15、 6:54 AM Discrete Math. , Chen Chen13图的度数列图的度数列设设无无向向图图G的的顶顶点点集集V=v1, v2, , vnG的度数列的度数列: d(v1), d(v2), , d(vn)如右图度数列如右图度数列:4,4,2,1,3设设有有向向图图D的的顶顶点点集集V=v1, v2, , vnD的度数列的度数列: d(v1), d(v2), , d(vn)D的出度列的出度列: d+(v1), d+(v2), , d+(vn)D的入度列的入度列: d (v1), d (v2), , d (vn)e1e2e3e4e5e6e7v5v1v2v3v4e1e2e3e4e5e
16、6e7dabc对于给定的非负整数列对于给定的非负整数列d=(d1,d2,dn),若存在以若存在以V=v1,v2,vn为顶点集的为顶点集的n阶无向图阶无向图G, 使得使得d(vi)=di, 则称则称d是是可图化的可图化的。特别地，若所得图是简单图，则称特别地，若所得图是简单图，则称d是是可简单图化的可简单图化的。 左图度数列左图度数列:5,3,3,3 出度列出度列:4,0,2,1 入度列入度列:1,3,1,2CHAPTER CHAPTER FourteenFourteen7/25/2024 6:54 AM Discrete Math. , Chen Chen14(2) 能能例例1 下述下述2组数
17、能成为无向图的度数列吗组数能成为无向图的度数列吗? (1) 3,3,3,4; (2) 1,2,2,3解解 (1) 不可能不可能. . 有奇数个奇数有奇数个奇数. .可图化可图化定理定理11.3 设非负整数列设非负整数列 d=(d1 , d2 , dn)，则，则d是可图化的当且是可图化的当且仅当仅当 定理定理11.4设设G为任意为任意n阶无向简单图，则阶无向简单图，则(G)n-1.CHAPTER CHAPTER FourteenFourteen7/25/2024 6:54 AM Discrete Math. , Chen Chen15实例实例例例11.2 判断下列各非负整数哪些是可图化的？哪些可
18、简单图化判断下列各非负整数哪些是可图化的？哪些可简单图化？(1)（5,5,4,4,2,1） (2) (5,4,3,2,2) (3) (3,3,3,1)(5) (4,4,3,3,2,2)解：除（解：除（1）外均可）外均可图化，而且只有（化，而且只有（5）可）可简单图化。化。 (4) (d1,d2,dn), d1d2,dn=1且且CHAPTER CHAPTER FourteenFourteen7/25/2024 6:54 AM Discrete Math. , Chen Chen16同构同构图之间的同构关系图之间的同构关系可看成全体图集合上的二元关系，这个二可看成全体图集合上的二元关系，这个二元关
19、系具有自反性，对称性和传递性，因而它是元关系具有自反性，对称性和传递性，因而它是等价关系等价关系。在这个等价关系的每个等价类中均取一个非标定图作为一个在这个等价关系的每个等价类中均取一个非标定图作为一个代表，凡与它同构的图，在同构的意义下都可以看成一个图。代表，凡与它同构的图，在同构的意义下都可以看成一个图。到目前为止，还没找到判断两个图是否同构的有效的算法。到目前为止，还没找到判断两个图是否同构的有效的算法。定义定义11.5 设设G1=, G2=为两个无向图为两个无向图(有向图有向图), 若存在双射函数若存在双射函数 f: V1V2, 使得对于任意的使得对于任意的vi,vj V1, (vi,
20、vj) E1 ( E1) 当且仅当当且仅当 (f(vi), f(vj) E2 ( E2)并且并且 (vi,vj) () 与与 (f(vi),f(vj) ()的重数相同，的重数相同，则称则称G1与与G2是同构的，记作是同构的，记作G1 G2.CHAPTER CHAPTER FourteenFourteen7/25/2024 6:54 AM Discrete Math. , Chen Chen17实例实例CHAPTER CHAPTER FourteenFourteen7/25/2024 6:54 AM Discrete Math. , Chen Chen18实例实例例例 画出画出3个以个以1,1,
21、1,2,2,3为度数列的非同构的无向简单图为度数列的非同构的无向简单图.CHAPTER CHAPTER FourteenFourteen7/25/2024 6:54 AM Discrete Math. , Chen Chen19实例实例例例11.3 画出画出4阶阶3条边的所有非同构的无向简单图条边的所有非同构的无向简单图.解解 总度数为总度数为6, 分配给分配给4个顶点个顶点, 最大度为最大度为3, 且奇度顶点数为且奇度顶点数为偶数偶数,有下述有下述3个度数列个度数列: (1) 1,1,1,3;(2)1,1,2,2;(3)0,2,2,2.1,1,1,31,1,2,20,2,2,2CHAPTER
22、 CHAPTER FourteenFourteen7/25/2024 6:54 AM Discrete Math. , Chen Chen20完全图与正则图完全图与正则图定义定义11.6 无向完全图无向完全图G: 每对顶点之间都有一条边的无向简单图每对顶点之间都有一条边的无向简单图. n 阶无向完全图记作阶无向完全图记作Kn, 顶点数顶点数 n, 边数边数 m=n(n 1)/2, = =n 1.有有向向完完全全图图D: 每每对对顶顶点点之之间间均均有有两两条条方方向向相相反反的的边边的的有有向向简简单单图图. 顶点数顶点数n, 边数边数m=n(n 1), += += = =n 1, = =2(
23、n 1).N阶竞赛图阶竞赛图D: D为为有向简单图有向简单图,且它的基图为且它的基图为Kn. 顶点数顶点数n, 边数边数m=n(n 1)/2.定义定义11.7 k-正则图正则图: 每个顶点的度数均为每个顶点的度数均为 k 的无向简单图的无向简单图. 顶点数顶点数 n, 边数边数 m=kn/2.CHAPTER CHAPTER FourteenFourteen7/25/2024 6:54 AM Discrete Math. , Chen Chen21实例实例K3K53阶有向完全图阶有向完全图2正则图正则图4正则图正则图3正则图正则图CHAPTER CHAPTER FourteenFourteen7
24、/25/2024 6:54 AM Discrete Math. , Chen Chen22子图子图定定义义11.8 设设G=, G =是是两两个个图图(同同为为无无向向,或或同为有向图同为有向图). 若若VV且且EE, 则则称称G 为为G的的子子图图, G为为G 的的母母图图, 记作记作GG. 若若VV或或EE, 称称G 为为G的的真子图真子图. 若若GG 且且V =V, 则称则称G 为为G的的生成子图生成子图. 设设VV且且V, 以以V 为为顶顶点点集集, 以以两两端端点点都都在在V 中中的所有边为边集的的所有边为边集的G的子图称作的子图称作V 的导出子图的导出子图, 记作记作GV . 设设
25、EE且且E, 以以E 为边集为边集, 以以E 中边关联的所有中边关联的所有顶点为顶点集的顶点为顶点集的G的子图称作的子图称作E 的导出子图的导出子图, 记作记作GE .CHAPTER CHAPTER FourteenFourteen7/25/2024 6:54 AM Discrete Math. , Chen Chen23实例实例(1),(2),(3)是是(1)的子图的子图, (2),(3)是真子图是真子图, (1)是母图是母图.(1),(3)是是(1)的生成子图的生成子图.(2)是是d,e,f 的导出子图的导出子图, 也是也是e5, e6, e7导出子图导出子图.(3)是是e1, e3, e
26、5, e7的导出子图的导出子图.aabbccdddeee f f f e1 e1 e2 e3 e3 e4 e5 e5 e5 e6 e6 e7 e7 e7(1)(2)(3)CHAPTER CHAPTER FourteenFourteen7/25/2024 6:54 AM Discrete Math. , Chen Chen24补图补图定义定义11.9 设设G=为为n阶无向简单图阶无向简单图, 记记 =V V E, 称称 为为G的的补图补图.abcde f e1 e3 e5 e7(2)eabcd f e1 e2 e3 e4 e5 e6 e7(1), 称称G是自是自补图补图.若若CHAPTER CH
27、APTER FourteenFourteen7/25/2024 6:54 AM Discrete Math. , Chen Chen25从图中删边、从图中删边、 点集合点集合定义定义11.10 设设G=为无向图为无向图。 记记 G e : 从从G中删除中删除e G E : 从从G中删除中删除E 中所有边中所有边 G v: 从从G中删除中删除v及关联的边及关联的边 G V : 从从G中删除中删除V 中所有的顶点及关联的边中所有的顶点及关联的边 G e : 从从G中删除中删除e后将后将e的两个端点用一个新的顶点代替的两个端点用一个新的顶点代替. G+(u, v): 在在u, v之间加一条边之间加一
28、条边CHAPTER CHAPTER FourteenFourteen7/25/2024 6:54 AM Discrete Math. , Chen Chen26例子例子e4v2v1v3v4v5v6v8e1e2e3e5e6e7e8G:G e1 :e4v2v1v3v4v5v6v8e2e3e5e6e7e8G e2,e5:e4v2v1v3v4v5v6v8e1e3e6e7e8G v5 :e4v2v1v3v4v6v8e1e2e5e8G e6 :e4v2v1v3wv6v8e1e2e3e5e7e8G+(v1, v2):e4v2v1v3v4v5v6v8e1e2e3e5e6e7e8e9CHAPTER CHAPTE
29、R FourteenFourteen7/25/2024 6:54 AM Discrete Math. , Chen Chen2711.2通路与回路通路与回路定义定义11.11 给定图给定图G=为无向标定图为无向标定图, G中顶点与边的交替序列中顶点与边的交替序列 =v0e1v1e2elvl. 其中其中1 i l, ei=(vi 1,vi), 则称则称 为为v0到到vl的的通路通路, v0和和vl分别为通路的分别为通路的起点起点和和终点终点, l(边的条数边的条数)为通路的为通路的长度长度. 又若又若v0=vl, 则称则称 为为回路回路. 若通路中所有边各异若通路中所有边各异, 则称为则称为简单
30、通路简单通路. 若回路中所有边各异若回路中所有边各异, 则称为则称为简单回路简单回路. 否则称为否则称为复杂通路复杂通路(复杂回路复杂回路). 若通路若通路 中所有顶点各异中所有顶点各异, 则称则称 为为初级通路或路径初级通路或路径. 若回路中所有顶点若回路中所有顶点(除除v0=vl)各异各异, 则称则称 为为初级回路或圈初级回路或圈. 长度为奇数的圈称作长度为奇数的圈称作奇圈奇圈. 长度为偶数的圈称作长度为偶数的圈称作偶圈偶圈. CHAPTER CHAPTER FourteenFourteen7/25/2024 6:54 AM Discrete Math. , Chen Chen28说明说明
31、(1) 表示方法表示方法 按定义用顶点和边的交替序列按定义用顶点和边的交替序列, =v0e1v1e2elvl 用边序列用边序列, =e1e2el 简单图中简单图中, 用顶点序列用顶点序列, =v0v1vl(2) 在无向图中在无向图中, 长度为长度为1的圈由环构成的圈由环构成. 长度为长度为2的圈由两条平行边构成的圈由两条平行边构成. 在无向简单图中在无向简单图中, 所有圈的长度所有圈的长度 3. 在有向图中在有向图中, 长度为长度为1的圈由环构成的圈由环构成. 在有向简单图中在有向简单图中, 所有圈的长度所有圈的长度 2.CHAPTER CHAPTER FourteenFourteen7/25
32、/2024 6:54 AM Discrete Math. , Chen Chen29说明说明(续续)(3) 初级通路初级通路(回路回路)是简单通路是简单通路(回路回路), 但反之不真但反之不真.初级通路初级通路非初级的简单通路非初级的简单通路初级回路初级回路非初级的非初级的简单回路简单回路CHAPTER CHAPTER FourteenFourteen7/25/2024 6:54 AM Discrete Math. , Chen Chen30通路与回路通路与回路(续续)定理定理11.5 在在n阶图阶图G中中, 若从顶点若从顶点u到到v(u v)存在通路存在通路, 则从则从u到到v存在长度小于等
33、于存在长度小于等于n 1的通路的通路.证证 若通路中没有相同的顶点若通路中没有相同的顶点(即初级通路即初级通路), 长度必长度必 n 1.若有相同的顶点若有相同的顶点, 删去这两个顶点之间的这一段删去这两个顶点之间的这一段, 仍是仍是u到到v的通的通路路. 重复进行重复进行, 直到没有相同的顶点为止直到没有相同的顶点为止.推论推论 在在n阶图阶图G中中, 若从顶点若从顶点u到到v(u v)存在通路存在通路, 则从则从u到到v一定一定存在长度小于或等于存在长度小于或等于n 1的初级通路的初级通路.定理定理11.6 在在n阶图中阶图中, 若存在若存在v到自身的回路到自身的回路, 则一定存在则一定存
34、在v到自身到自身长度小于等于长度小于等于n的回路的回路.推论推论 在在n阶图中阶图中, 若存在若存在v到自身的简单回路到自身的简单回路, 则一定存在则一定存在v到自到自身长度小于等于身长度小于等于n的初级回路的初级回路.CHAPTER CHAPTER FourteenFourteen7/25/2024 6:54 AM Discrete Math. , Chen Chen3111.3 图的连通性图的连通性定义定义11.12设无向图设无向图G=, u,v Vu与与v连通连通: 若若u与与v之间有通路之间有通路,记为记为u v.规定规定u u. 连通关系连通关系 R=| u,v V且且u v, 则可
35、验证则可验证R是等价关系是等价关系.定义定义11.13 连通图连通图: 任意两点都连通的图任意两点都连通的图. 规定平凡图是连通图规定平凡图是连通图. 非非连通图连通图:不是连通图的图不是连通图的图.定定义义11.14 连连通通分分支支:设设V/R=V1,V2,Vk, 称称V关关于于R的的等等价价类的导出子图类的导出子图GV1,GV2,GVk 为为G的连通分支的连通分支.连通分支数连通分支数 p(G)=k.G是连通图是连通图 p(G)=1.CHAPTER CHAPTER FourteenFourteen7/25/2024 6:54 AM Discrete Math. , Chen Chen32
36、短程线与距离短程线与距离定义定义11.15 设无向图设无向图G=, u,v V.若若u v, u与与v之间的短程线之间的短程线: u与与v之间长度最短的通路之间长度最短的通路. u与与v之间的距离之间的距离d(u,v): u与与v之间短程线的长度之间短程线的长度.若若u与与v不连通不连通, 规定规定d(u,v)=.性质：性质：(1) d(u,v) 0, 且且d(u,v)=0 u=v(2) d(u,v)=d(v,u)(3) d(u,v)+d(v,w) d(u,w) 例如例如 a与与e之间的短程线之间的短程线:ace,afe. d(a,e)=2, d(a,h)= abcde f ghiCHAPTE
37、R CHAPTER FourteenFourteen7/25/2024 6:54 AM Discrete Math. , Chen Chen33点割集与边割集点割集与边割集定定义义11.16 设设无无向向图图G=,若若V V且且V , 使使得得p(G V )p(G),而对而对 V V , p(G V )=p(G), 则称则称V 为为G的的点割集点割集. 定义定义11.17若若E E, E ,使得使得p(G E )p(G),而对而对 E E , p(G E )=p(G), 则称则称E 为为G的的边割集边割集. 若若v为点割集为点割集, 则称则称v为为割点割点.若若e为边割集为边割集, 则称则称e
38、为为割边割边或或桥桥.例例e4v2v1v3v4v5v6e1e2e3e5e6点割集：点割集：v2, v4, v3, v5割点：割点：v3, v5边割集边割集:e5,e6,e1,e2,e1,e3,e1,e4, e2,e3,e2,e4,e3,e4桥桥: e5,e6 CHAPTER CHAPTER FourteenFourteen7/25/2024 6:54 AM Discrete Math. , Chen Chen34实例实例说明：说明：Kn无点割集无点割集. n 阶零图既无点割集，也无边割集阶零图既无点割集，也无边割集.若若G连通，连通，E 为边割集，则为边割集，则p(G E )=2.若若G连通，
39、连通，V 为点割集，则为点割集，则p(G V ) 2.abcde fge1e2e3e4e5e6e7e8e9e, f点割集点割集:e,f ,割点割点:c,d 桥桥: e8,e9边割集边割集:e8,e9, e1,e2,e1, e3, e6, e1, e3, e4, e7CHAPTER CHAPTER FourteenFourteen7/25/2024 6:54 AM Discrete Math. , Chen Chen35点连通度与边连通度点连通度与边连通度定义定义11.18 设无向连通图设无向连通图G=,称称 (G)=min |V | | V 是是G的点割集的点割集为为G的的点连通度点连通度.例
40、如例如3 (G)=3 (G)=定义定义11.19 设无向连通图设无向连通图G=,称称 (G)=min |E | | E 是是G的边割集的边割集 为为G的的边连通度边连通度.若若 (G)k, k为非负整数为非负整数,则称则称G是是k-连通图连通图. 若若 (G)r，则称，则称G是是r边边-连通图。连通图。若若G是是r边边-连通图连通图, 则在则在G中删除任意中删除任意r-1条边后条边后, 所得图是所得图是 连通的连通的.若若G是是k-连通图连通图,则在则在G中删除任何中删除任何k-1个顶点后个顶点后,所得图是所得图是连通的连通的.CHAPTER CHAPTER FourteenFourteen7
41、/25/2024 6:54 AM Discrete Math. , Chen Chen36点连通度与边连通度点连通度与边连通度(续续)说明说明:(1) 若若G是平凡图是平凡图, 则则 (G)=0, (G)=0.(2) 若若G是完全图是完全图Kn, 则则 (G)=n 1, (G)= n 1.(3) 若若G中存在割点中存在割点, 则则 (G)=1; 若若G中存在割边中存在割边, 则则 (G)= 1.(4) 规定非连通图的点连通度和边连通度均为规定非连通图的点连通度和边连通度均为0.定理定理11.7 对任何无向图对任何无向图G, 有有 (G) (G) (G).(5)设设G1,G2都是都是n阶阶无向简
42、单图无向简单图，若若(G1)(G2)，则称，则称G1比比G2的点连通程度高的点连通程度高.若若(G1)(G2)，则称，则称G1比比G2的边连通程度高的边连通程度高.例例: P280图图11.9CHAPTER CHAPTER FourteenFourteen7/25/2024 6:54 AM Discrete Math. , Chen Chen37有向图的连通性及其分类有向图的连通性及其分类定义定义11.20 设有向图设有向图D=, u,v V, u可达可达v: u到到v有通路有通路. 规定规定u到自身总是可达的到自身总是可达的. u与与v相互可达相互可达: u可达可达v且且v可达可达u定义定义
43、11.22 设有向图设有向图D=, D弱连通弱连通(连通连通): 略去各边的方向所得无向图为连通图略去各边的方向所得无向图为连通图 D单向连通单向连通: u,v V，u可达可达v 或或v可达可达u D强连通强连通: u,v V，u与与v相互可达相互可达定理定理11.8 D是强连通的当且仅当是强连通的当且仅当D中存在经过所有顶点的回路中存在经过所有顶点的回路定理定理11.9 D是单向连通的当且仅当是单向连通的当且仅当D中存在经过所有顶点的通路中存在经过所有顶点的通路CHAPTER CHAPTER FourteenFourteen7/25/2024 6:54 AM Discrete Math. ,
44、 Chen Chen38实例实例 强连通强连通单连通单连通弱连通弱连通CHAPTER CHAPTER FourteenFourteen7/25/2024 6:54 AM Discrete Math. , Chen Chen39有向图中的短程线与距离有向图中的短程线与距离定义定义11.21 设有向图设有向图D=, u,v V, 如果如果u可达可达v,u到到v的短程线的短程线: u到到v长度最短的通路长度最短的通路距离距离d: u到到v的短程线的长度的短程线的长度若若u不可达不可达v, 规定规定d=.性质：性质： d 0, 且且d=0 u=v d+d d 注意注意: 没有对称性没有对称性CHAPT
45、ER CHAPTER FourteenFourteen7/25/2024 6:54 AM Discrete Math. , Chen Chen40例题例题 例例1 在仅两个奇次顶的无向图中，此二奇次顶连通在仅两个奇次顶的无向图中，此二奇次顶连通 证证 如果图如果图G G中恰好有两个奇次顶中恰好有两个奇次顶u,vu,v， 但在但在G G中这两个奇次项中这两个奇次项u,vu,v不连通，不连通， 则存在则存在G G的两个连通片的两个连通片G G1 1与与G G2 2，使得，使得u uV(GV(G1 1), v), vV(GV(G2 2) )。 对于连通图对于连通图G G1 1与与G G2 2来说皆有
46、来说皆有1 1个奇次项个奇次项 与定理与定理11.111.1的推论相矛盾。的推论相矛盾。CHAPTER CHAPTER FourteenFourteen7/25/2024 6:54 AM Discrete Math. , Chen Chen41扩大路径法扩大路径法-最长轨最长轨(极大路径极大路径)法法 设设G=为为n阶阶无无向向图图,E.设设是是G中中一一条条路路径径,若若此此路路径径 l 的的始始点点或或终终点点与与通通路路外外的的顶顶点点相相邻邻,则则将将他他们们扩扩到到通通路路中中,继继续续这这过过程程,直直到到最最后后得得到到的的通通路的始点和终点不与通路外的顶点相邻为止路的始点和终点
47、不与通路外的顶点相邻为止. 设最后得到的路径为设最后得到的路径为 l +k ,称它为称它为极大路径极大路径.利用这种方法我们可以找到图利用这种方法我们可以找到图G的最长轨的最长轨.例例例例 无零次与无零次与无零次与无零次与1 1次顶的单图中有圈次顶的单图中有圈次顶的单图中有圈次顶的单图中有圈. .证证 由于此图由于此图G中无零次与中无零次与1次顶所以对于每个顶次顶所以对于每个顶v，d(v) 2,且存在一条最长轨且存在一条最长轨P(u0,v0) ：v0u0这种边的另一端必在这种边的另一端必在P(u0,v0)上，不然上，不然P(u0,v0)还可以加长，还可以加长，与与P(u0,v0)最长相违最长相
48、违.于是造成如图所示的情形于是造成如图所示的情形这样这样u0,v0还至少各有一条不在还至少各有一条不在P(u0,v0)上的边与之关联，上的边与之关联，从而从而G中有圈中有圈.v0u0e2e1CHAPTER CHAPTER FourteenFourteen7/25/2024 6:54 AM Discrete Math. , Chen Chen42例例 若图若图G是连通图，是连通图，G1是是G的子图，的子图，|V(G1)|V(G)|,则则G中有不中有不属于属于G1的边的边e,e的一端属于的一端属于V(G1)，另一端不属于，另一端不属于V(G1)。考虑最长轨考虑最长轨v0vm。则存在。则存在vivj
49、,1ijm使使vi , vj与与v0相邻。相邻。最后考虑最后考虑i,j的奇偶性即可。的奇偶性即可。v1v2vivjvmv0例例11.8 若若G是是n阶无向简单图阶无向简单图,每顶次数不小于每顶次数不小于3,则则G中有偶圈。中有偶圈。v1v2vivuCHAPTER CHAPTER FourteenFourteen7/25/2024 6:54 AM Discrete Math. , Chen Chen43二部图二部图 定义定义11.23 设设G=,若能将若能将V分成分成V1和和V2(V1V2=V, V1V2=),使使得得G中的每条边的两个端点都是一个属于中的每条边的两个端点都是一个属于V1,另一个
50、属于另一个属于V2,则称则称G为为二部图二部图(二分图二分图, 偶图偶图)，记为，记为。 称称V1与与V2为为互补顶点子集互补顶点子集. 若若G为为简单二部图简单二部图, V1中每个顶点均与中每个顶点均与V2中所有顶点相邻中所有顶点相邻, 则称则称G为为完全二部图完全二部图, 记为记为Kr,s, r=|V1|, s=|V2|. 定理定理11.10 一个无向图一个无向图G是是二部图二部图当且仅当当且仅当G中无奇数长度的回路中无奇数长度的回路。分析分析: 必要性必要性: G有回路有回路每个圈为偶圈每个圈为偶圈,利用顶点划分利用顶点划分。充分性充分性: 考虑连通性考虑连通性,然后根据跟某个点的距离的
51、奇偶性划分顶点集合然后根据跟某个点的距离的奇偶性划分顶点集合.K23K33CHAPTER CHAPTER FourteenFourteen7/25/2024 6:54 AM Discrete Math. , Chen Chen44二部图的判别定理证明二部图的判别定理证明证证 必要性必要性. 设设G=是二部图是二部图, 每条边只能从每条边只能从V1到到V2, 或从或从V2到到V1, 故任何回路必为偶长度故任何回路必为偶长度.充分性充分性. 不妨设不妨设G至少有一条边且连通至少有一条边且连通. 取任一顶点取任一顶点u, 令令 V1=v | v V d(v,u)为偶数为偶数, V2=v | v V
52、d(v,u)为奇数为奇数则则V1 V2=V, V1 V2=. 先证先证V1中任意两点不相邻中任意两点不相邻. 假设存在假设存在s,t V1, e=(s,t) E. 设设 1, 2分别是分别是u到到s,t的短程线的短程线, 则则 1 e 2是一条回路是一条回路, 其长度为奇数其长度为奇数, 与假设矛盾与假设矛盾. 同理可同理可证证V2中任意两点不相邻中任意两点不相邻. CHAPTER CHAPTER FourteenFourteen7/25/2024 6:54 AM Discrete Math. , Chen Chen45实例实例非二部图非二部图非二部图非二部图CHAPTER CHAPTER F
53、ourteenFourteen7/25/2024 6:54 AM Discrete Math. , Chen Chen4611.4 图的矩阵表示图的矩阵表示无向图的关联矩阵无向图的关联矩阵有向无环图的关联矩阵有向无环图的关联矩阵有向图的邻接矩阵有向图的邻接矩阵n有向图中的通路数与回路数有向图中的通路数与回路数有向图的可达矩阵有向图的可达矩阵CHAPTER CHAPTER FourteenFourteen7/25/2024 6:54 AM Discrete Math. , Chen Chen47无向图的关联矩阵无向图的关联矩阵定义定义11.24 设无向图设无向图G=, V=v1, v2, , v
54、n, E=e1, e2, , em. 令令mij为为vi与与ej的的关联次数关联次数, 称称(mij)n m为为G的关联矩阵的关联矩阵, 记为记为M(G). mij的可能取值为的可能取值为:0,1,2.例如例如e1e2e3e4e5e6v5v1v2v3v42 1 1 0 0 00 1 0 1 1 10 0 0 0 1 10 0 0 0 0 00 0 1 1 0 0 M(G)=例子例子:P284图图11.14CHAPTER CHAPTER FourteenFourteen7/25/2024 6:54 AM Discrete Math. , Chen Chen48关联矩阵的性质关联矩阵的性质(6)
55、ej是环是环 第第j列的一个元素为列的一个元素为2, 其余为其余为0(4) ei 与与ei是平行边是平行边 第第j列与第列与第k列相同列相同(5) vi是孤立点是孤立点 第第i行全为行全为0CHAPTER CHAPTER FourteenFourteen7/25/2024 6:54 AM Discrete Math. , Chen Chen49无环有向图的关联矩阵无环有向图的关联矩阵则称则称(mij)n m为为D的关联矩阵的关联矩阵, 记为记为M(D).定义定义11.25 设无环有向图设无环有向图D=, V=v1, v2, , vn, E=e1, e2, , em. 令令(3) ej与与ek是
56、平行边是平行边 第第j列与第列与第k列相同列相同(2) 第第i行行1的个数等于的个数等于d+(v), 第第i行行 1的个数等于的个数等于d (v)性质性质:例子例子:P285图图11.15CHAPTER CHAPTER FourteenFourteen7/25/2024 6:54 AM Discrete Math. , Chen Chen50实例实例v1v2v3v4e2e1e3e4e5e6e7 1 1 0 0 0 1 1 0 1 1 0 0 0 0 0 0 1 1 1 1 1 1 0 0 1 1 0 0M(D)=CHAPTER CHAPTER FourteenFourteen7/25/2024
57、 6:54 AM Discrete Math. , Chen Chen51有向图的邻接矩阵有向图的邻接矩阵设有向图设有向图D=, V=v1, v2, , vn, E=e1, e2, , em, 令令 为顶点为顶点vi邻接到顶点邻接到顶点vj边的条数，称边的条数，称( )m n为为D的邻接矩阵的邻接矩阵, 记作记作A(D), 简记作简记作A.例子例子:P286图图11.16定义定义11.26CHAPTER CHAPTER FourteenFourteen7/25/2024 6:54 AM Discrete Math. , Chen Chen52实例实例1 1 0 00 0 1 01 0 0 01
58、 0 2 0A=v1v2v3v4CHAPTER CHAPTER FourteenFourteen7/25/2024 6:54 AM Discrete Math. , Chen Chen53有向图中的通路数与回路数有向图中的通路数与回路数定理定理11.11 设设A为为n阶有向图阶有向图D的邻接矩阵的邻接矩阵, 则则Al(l 1)中元素中元素 等于等于D中中vi到到vj长度为长度为 l 的通路的通路(含回路含回路)数数, 等于等于vi到自身长到自身长度为度为l 的回路数的回路数, 等于等于D中中长度为长度为 l 的通路的通路(含回路含回路)总数总数, 等于等于D中中长度为长度为 l 的的回路总数回
59、路总数. 推论推论 设设Bl=A+A2+Al(l 1), 则则Bl中元素中元素 等于等于D中中vi到到vj长度小于等于长度小于等于 l 的通路的通路(含回路含回路)数数, 等于等于D中中vi到到vi的长的长度小于等于度小于等于 l 的回路数的回路数, 等于等于D中中长度小于等于长度小于等于l 的通路的通路(含回路含回路)数数, 为为D中中长度小于等于长度小于等于l 的回路数的回路数.CHAPTER CHAPTER FourteenFourteen7/25/2024 6:54 AM Discrete Math. , Chen Chen54实例实例(续续) 说明说明: 在这里在这里, 通路和回路数
60、是定义意义下的通路和回路数是定义意义下的.A=1 1 0 00 0 1 01 0 0 01 0 2 0A2=1 1 1 01 0 0 01 1 0 03 1 0 0A3=2 1 1 01 1 0 01 1 0 03 3 1 0A4=3 2 1 01 1 0 02 1 1 04 3 1 0v1到到v2长为长为3的通路有的通路有1条条v1到到v3长为长为3的通路有的通路有1条条v1到自身长为到自身长为3的回路有的回路有2条条D中长为中长为3的通路共有的通路共有15条条,其中回路其中回路3条条v1v2v3v4CHAPTER CHAPTER FourteenFourteen7/25/2024 6:54
61、 AM Discrete Math. , Chen Chen55有向图的可达矩阵有向图的可达矩阵性质性质:P(D)主对角线上的元素全为主对角线上的元素全为1. D强连通当且仅当强连通当且仅当P(D)的元素全为的元素全为1.设有向图设有向图D=, V=v1, v2, , vn, 令令 称称(pij)n n为为D的可达矩阵的可达矩阵, 记作记作P(D), 简记为简记为P. 定义定义11.27CHAPTER CHAPTER FourteenFourteen7/25/2024 6:54 AM Discrete Math. , Chen Chen56实例实例例例1 (1) v1到到v4,v4到到v1长为
62、长为3的通路各有多少条的通路各有多少条?(2) v1到自身长为到自身长为1,2,3,4的回路各有多少条的回路各有多少条?(3) 长为长为4的通路共有多少条的通路共有多少条?其中有多少条回路其中有多少条回路?(4) 长度小于等于长度小于等于4的回路共有多少条的回路共有多少条?(5) 写出写出D的可达矩阵的可达矩阵, 并问并问D是强连通的吗是强连通的吗?v1v2v3v4A=1 2 1 00 0 1 00 0 0 10 0 1 0CHAPTER CHAPTER FourteenFourteen7/25/2024 6:54 AM Discrete Math. , Chen Chen57实例实例(续续)v1到到v4长为长为3的通路有的通路有 条条,A2=1 2 3 10 0 0 10 0 1 00 0 0 1A3=1 2 4 30 0 1 00 0 0 10 0 1 0A4=1 2 6 40 0 0 10 0 1 00 0 0 13v4到到v1长为长为3的通路有的通路有 条条0v1到自身长为到自身长为1,2,3,4的回路各有的回路各有 条条1长为长为4的通路共有的通路共有 条，其中有条，其中有 条回路条回路163长度小于等于长度小于等于4的回路共有的回路共有 条条8可达矩阵可达矩阵非强连通非强连通,单连通单连通 P=1 1 1 10 1 1 10 0 1 10 0 1 1解解
