为连通分支课件.ppt

1、1第五部分第五部分 图论图论 图论图论(Graph Theory)是数学的一个分支。它以图为研究对是数学的一个分支。它以图为研究对象。图论中的图是由若干给定的点及连接两点的线所构成的图象。图论中的图是由若干给定的点及连接两点的线所构成的图形，这种图形通常用来描述事物之间的某种关系，用点代表事形，这种图形通常用来描述事物之间的某种关系，用点代表事物，用连接两点的线表示相应两个事物间具有这种关系。物，用连接两点的线表示相应两个事物间具有这种关系。 图论起源于著名的哥尼斯堡七桥问题。欧拉在图论起源于著名的哥尼斯堡七桥问题。欧拉在1736年用图年用图的形式解决了这个问题，证明了这个问题没有解，这项工作

2、使的形式解决了这个问题，证明了这个问题没有解，这项工作使欧拉成为图论的创始人。欧拉成为图论的创始人。 作为描述事务之间关系的手段和工具，目前，图论在许多作为描述事务之间关系的手段和工具，目前，图论在许多领域，诸如，计算机科学、物理学、化学、运筹学、信息论、领域，诸如，计算机科学、物理学、化学、运筹学、信息论、控制论、网络通讯、社会科学以及经济管理、军事、国防、工控制论、网络通讯、社会科学以及经济管理、军事、国防、工农业生产等方面都得到广泛的应用，也正是因为在众多方面的农业生产等方面都得到广泛的应用，也正是因为在众多方面的应用中，图论自身才得到了非常迅速的发展。应用中，图论自身才得到了非常迅速的

3、发展。 2第十四章第十四章 图的基本概念图的基本概念主要内容主要内容l 图图l 通路与回路通路与回路l 图的连通性图的连通性l 图的矩阵表示图的矩阵表示l 图的运算图的运算预备知识预备知识l 无序积无序积A B=a,b | a A b B，(与笛卡尔积区别与笛卡尔积区别)无序对无序对a,b记作记作(a,b)，并且，并且(a,b) = (b,a)l 多重集合多重集合元素可以重复出现的集合元素可以重复出现的集合314.1 图图定义定义14.1 无向图无向图G是一个有序二元组是一个有序二元组G = , 其中其中(1) V是非空有穷集，称为是非空有穷集，称为顶点集顶点集，其中的元素称为，其中的元素称为

4、顶点顶点(2) E是是无序积无序积V V 的的有穷多重子集有穷多重子集，称为，称为边集边集，其元素称，其元素称为为无向边无向边，简称，简称边边实例实例 设设 V = v1, v2, ,v5, E = (v1,v1), (v1,v2), (v2,v3), (v2,v3), (v2,v5), (v1,v5), (v4,v5) 则则G = 是无向图，如右图所示是无向图，如右图所示4有向图有向图定义定义14.2 有向图有向图D=, 只需注意只需注意E是是笛卡尔积笛卡尔积V V 的的有有穷多重子集穷多重子集。下图表示的是一个有向图，试写出它的。下图表示的是一个有向图，试写出它的V 和和 E V =a,b

5、,c,dE =,注意：图的注意：图的数学定义数学定义（D=）与）与图形表示图形表示（上图上图）都要）都要熟练掌握，要能够把两者互相对应起来熟练掌握，要能够把两者互相对应起来5相关概念相关概念1. 图图 无向图无向图G，有向图，有向图D（有时也用（有时也用G泛指图）泛指图） V(G), E(G), V(D), E(D)，用，用 ek 表示无向边或有向边表示无向边或有向边2. n阶图阶图3. 零图，零图，n 阶零图阶零图Nn与平凡图与平凡图N14. 规定：空图规定：空图5. 标定图与非标定图，基图标定图与非标定图，基图6. 顶点与边的关联关系顶点与边的关联关系 关联、关联次数关联、关联次数 环环

6、孤立点孤立点7. 顶点之间的相邻与边相邻顶点之间的相邻与边相邻6)()()(),()(|)(vvNvNvvuGEvuGVuuvNv 的的闭闭邻邻域域的的邻邻域域)(|)(关关联联与与veGEeevI )()()()()()(,)(|)()(,)(|)(vvNvNvvvvNvvuDEvuDVuuvvvuDEuvDVuuvvDDDDDDD 的的闭闭邻邻域域的的邻邻域域的的先先驱驱元元集集的的后后继继元元集集8. 邻域与关联集邻域与关联集 v V(G) (G为无向图为无向图) v的关联集的关联集 v V(D) (D为有向图为有向图)相关概念相关概念7多重图与简单图多重图与简单图定义定义14.3 (1

7、) 无向图中的平行边及重数无向图中的平行边及重数 (2) 有向图中的平行边及重数（有向图中的平行边及重数（注意方向性注意方向性） (3) 多重图多重图含平行边的图含平行边的图 (4) 简单图简单图不含平行边，也不含环的图不含平行边，也不含环的图在定义在定义14.3中定义的简单图是极其重要的概念中定义的简单图是极其重要的概念 8顶点的度数顶点的度数定义定义14.4 (1) 设设G=为无向图为无向图, v V, d(v)v的度数的度数, 简称度简称度 (2) 设设D=为有向图为有向图, v V, d (v)v的出度的出度 d+(v)v的入度的入度 d(v)v的度或度数的度或度数 (3) (G)最大

8、度最大度, (G)最小度最小度 (4) +(D), +(D), (D), (D), (D), (D) (5) 悬挂顶点，悬挂边，奇度顶点与偶度顶点悬挂顶点，悬挂边，奇度顶点与偶度顶点注意：环在无向图和有向图中的度。注意：环在无向图和有向图中的度。9mvdnii2)(1 mvdvdmvdniiniinii 111)()(,2)(且且定理定理14.1 设设G=为任意无向图，为任意无向图，V=v1,v2,vn, |E|=m, 则则证证 G中每条边中每条边 (包括环包括环) 均有两个端点，所以在计算均有两个端点，所以在计算G中各顶中各顶点度数之和时，每条边均提供点度数之和时，每条边均提供2度，度，m

9、条边共提供条边共提供 2m 度度.本定理的证明类似于定理本定理的证明类似于定理14.1定理定理14.2 设设D=为任意有向图，为任意有向图，V=v1,v2,vn, |E|=m, 则则握手定理握手定理10握手定理推论握手定理推论推论推论 任何图任何图 (无向或有向无向或有向) 中，奇度顶点的个数是偶数中，奇度顶点的个数是偶数.证证 设设G=为任意图，令为任意图，令 V1=v | v V d(v)为奇数为奇数 V2=v | v V d(v)为偶数为偶数 则则V1 V2=V, V1 V2=，由握手定理可知，由握手定理可知由于由于2m, 均为偶数，所以均为偶数，所以 为偶数，但因为为偶数，但因为V1中

10、中顶点度数为奇数，所以顶点度数为奇数，所以|V1|必为偶数必为偶数. 21)()()(2VvVvVvvdvdvdm 2)(Vvvd 1)(Vvvd11例例1 无向图无向图G有有16条边，条边，3个个4度顶点，度顶点，4个个3度顶点，其余度顶点，其余顶点度数均小于顶点度数均小于3，问，问G的阶数的阶数n为几？为几？解解 本题的关键是应用握手定理本题的关键是应用握手定理. 设除设除3度与度与4度顶点外，还有度顶点外，还有x个顶点个顶点v1, v2, , vx， 则则 d(vi) 2，i =1, 2, , x，于是得不等式于是得不等式 32 24+2x得得 x 4, 阶数阶数 n 4+4+3=11.

11、 握手定理应用握手定理应用12图的度数列图的度数列1 . V=v1, v2, , vn为无向图为无向图G的顶点集，称的顶点集，称d(v1), d(v2), , d(vn)为为G的的度数列度数列 2. V=v1, v2, , vn为有向图为有向图D的顶点集，的顶点集， D的的度数列度数列：d(v1), d(v2), , d(vn) D的的入度列入度列：d+(v1), d+(v2), , d+(vn) D的的出度列出度列：d (v1), d (v2), , d (vn) 3. 非负整数列非负整数列d=(d1, d2, , dn)的的可图化可图化，可简单图化可简单图化.定理定理14.3：非负整数列：

12、非负整数列d可图化的充要条件可图化的充要条件 为偶数。为偶数。易知：易知：(2, 4, 6, 8, 10)是可图化的（不一定是惟一的图），而是可图化的（不一定是惟一的图），而 (3, 3, 3, 4)是不可图化的，是不可图化的，定理定理14.4：n阶无向简单图阶无向简单图G， (G)n-1.Vvvd)(13图的同构图的同构定义定义14.5 设设G1=, G2=为两个无向图为两个无向图(两个有向两个有向图图)，若存在双射函数，若存在双射函数f:V1V2, 对于对于vi,vj V1, (vi,vj) E1 当且仅当当且仅当 (f(vi),f(vj) E2 （ E1 当且仅当当且仅当 E2在有向图中

13、在有向图中)并且并且, (vi,vj)（）与）与 (f(vi),f(vj)（）的重数相）的重数相同，则称同，则称G1与与G2是是同构同构的，记作的，记作G1 G2. l 图之间的同构关系具有自反性、对称性和传递性图之间的同构关系具有自反性、对称性和传递性.l 能找到多条同构的必要条件，但它们都不是充分条件：能找到多条同构的必要条件，但它们都不是充分条件： 边数相同，顶点数相同边数相同，顶点数相同; 度数列相同等度数列相同等 若破坏必要条件，则两图不同构若破坏必要条件，则两图不同构l 判断两个图同构是个难题，至今没有找到简便的方法判断两个图同构是个难题，至今没有找到简便的方法14图同构的实例图同

14、构的实例图中图中(1)与与(2)的度数列相同，它们同构吗？为什么？的度数列相同，它们同构吗？为什么？ (1) (2) (3) (4) 图中，图中，(1)与与(2)不同构（度数列不同），不同构（度数列不同），(3)与与(4)也不同构也不同构. (1) (2) 15图同构的实例图同构的实例 - 彼得松图彼得松图16n 阶完全图与竞赛图阶完全图与竞赛图定义定义14.6 (1) n 阶阶无向完全图无向完全图每个顶点与其余顶点均相邻的每个顶点与其余顶点均相邻的 n 阶阶无无向简单图向简单图，记作，记作 Kn (n 1) .简单性质：边数简单性质：边数(2) n 阶阶有向完全图有向完全图每对顶点之间均有两

15、条方向相反的有每对顶点之间均有两条方向相反的有向边的向边的n阶阶有向简单图有向简单图.简单性质：简单性质： (3) n 阶阶竞赛图竞赛图基图为无向完全图基图为无向完全图Kn的的n 阶有向简单图阶有向简单图.简单性质：边数简单性质：边数1,2)1( nnnm 1),1(2),1( nnnnm 1,2)1( nnnm 17n 阶阶 k 正则图正则图(1)为为K5， (2)为为3阶有向完全图，阶有向完全图， (3)为为4阶竞赛图阶竞赛图. (1) (2) (3)定义定义14.7 k-正则图正则图所有顶点度数都为所有顶点度数都为k 的的n阶阶无向简单图无向简单图简单性质：边数（由握手定理得）简单性质：

16、边数（由握手定理得） = =k Kn是是 n 1-正则图，正则图，彼得松图是彼得松图是3-正则图正则图2nkm 18子图子图定义定义14.8 G=, G =（同为无向图或有向图同为无向图或有向图）(1) 若若VV且且EE，则称，则称G 为为G的的子图子图,GG，G为为G 的的母图母图(2) 若若VV或或EE，则称，则称G 为为G的的真子图真子图(3) 若若V =V且且EE ，则称，则称G 为为G的的生成子图生成子图(4) V 的的导出子图导出子图以以V （VV且且V）为顶点集，）为顶点集，V 在在母图母图G中所有出现过的边作为边集中所有出现过的边作为边集E 的子图，记作的子图，记作GV (5)

17、 E 的的导出子图导出子图以以E （EE且且E）为边集，）为边集，E 在在母母图图G中所有关联的顶点作为顶点集中所有关联的顶点作为顶点集V 的子图，记作的子图，记作GE 19实例实例例例2 画出画出K4的所有非同构的生成子图的所有非同构的生成子图20补图补图定义定义14.9 设设G=为为n阶阶无向简单图无向简单图，以，以V为顶点集，以为顶点集，以使使G成为完全图成为完全图Kn的所有添加边组成的集合为边集的图，称的所有添加边组成的集合为边集的图，称为为G的的补图补图，记作，记作 .若若G , 则称则称G是是自补图自补图. 相对于相对于K4, 求上面图中所有图的补图，并指出哪些是自补图求上面图中所

18、有图的补图，并指出哪些是自补图. 问：互为自补图的两个图的边数有何关系？问：互为自补图的两个图的边数有何关系？GG2114.2 通路与回路通路与回路定义定义14.11 给定图给定图G=（无向或有向的标定图），（无向或有向的标定图），G中中顶点与边的交替序列顶点与边的交替序列 = v0e1v1e2elvl，vi 1,vi 是是 ei 的端点的端点.（ei=(vi 1,vi )或或ei=）(1) 通路与回路：通路与回路： 就称为就称为v0到到vl的的通路通路，v0和和vl为为始点始点和和终点终点， 中中边的条数边的条数l 称为称为长度长度；若；若 v0=vl，则，则 称为称为回路回路.(2) 简单

19、通路与回路：若简单通路与回路：若 中中所有边各异，称所有边各异，称 为为简单通路简单通路，又若又若v0=vl， 称为称为简单回路简单回路(3) 初级通路初级通路(路径路径)与初级回路与初级回路(圈圈)： 中所有顶点各异，则中所有顶点各异，则称称 为为初级通路初级通路(路径路径)，又若，又若v0=vl，除，除v0外所有的顶点各外所有的顶点各不相同，则称不相同，则称 为为初级回路初级回路(圈圈)。奇圈，偶圈。奇圈，偶圈。(4) 复杂通路与回路：复杂通路与回路： 中有边重复出现中有边重复出现22几点说明几点说明初级通路初级通路(回路回路)一定是简单通路一定是简单通路(回路回路) ，简单通路，简单通路

20、(回路回路)一定一定是通路是通路(回路回路) ；反之不对；反之不对长为长为1的圈的圈(初级回路初级回路)只能由只能由环生成环生成；无向图中两条平行边构；无向图中两条平行边构成的圈长度为成的圈长度为2；无向简单图中，圈长；无向简单图中，圈长 3；有向简单图中圈；有向简单图中圈的长度的长度 2. 不同意义下圈的计数不同意义下圈的计数 在同构意义下，长度相同的圈只有在同构意义下，长度相同的圈只有1个，因为所有长度相个，因为所有长度相同的圈都是同构的。同的圈都是同构的。 在定义意义下，只要两个标记序列不同，就认为两个圈在定义意义下，只要两个标记序列不同，就认为两个圈不同。对于一个给定的长度为不同。对于

21、一个给定的长度为l的圈，在定义意义下，在无的圈，在定义意义下，在无向图中，可以衍生出向图中，可以衍生出2l个不同的圈，在有向图中则可以衍生个不同的圈，在有向图中则可以衍生出出l个不同的圈。个不同的圈。23通路与回路的性质通路与回路的性质定理定理14.5 在在n 阶图阶图G中，若从顶点中，若从顶点vi 到到vj（vi vj）存在通路，）存在通路，则从则从vi 到到 vj 存在长度小于或等于存在长度小于或等于n 1 的通路的通路.推论推论 在在 n 阶图阶图G中，若从顶点中，若从顶点vi 到到 vj（vi vj）存在通路，则）存在通路，则从从vi 到到vj 存在长度小于或等于存在长度小于或等于n

22、1的初级通路（路径）的初级通路（路径）.定理定理14.6 在一个在一个n 阶图阶图G中，若存在中，若存在 vi 到自身的回路，则一到自身的回路，则一定存在定存在vi 到自身长度小于或等于到自身长度小于或等于 n 的回路的回路.推论推论 在一个在一个n 阶图阶图G中，若存在中，若存在 vi 到自身的回路，则一定存到自身的回路，则一定存在长度小于或等于在长度小于或等于n 的初级回路的初级回路.2414.3 图的连通性图的连通性无向图的连通性无向图的连通性(1) 顶点之间的连通关系：顶点之间的连通关系：G=为无向图为无向图 若若 vi 与与 vj 之间有通路，则称之间有通路，则称vi,vj是是连通的

23、连通的，记作，记作vi vj规定：规定： v V，v v 是是V上的等价关系上的等价关系 R=| u,v V且且u v (2) G的连通性与连通分支的连通性与连通分支 若若 u,v V，u v，则称，则称G为为连通图，连通图，否则称否则称G非连通图非连通图 V/R=V1,V2,Vk，称导出子图，称导出子图GV1, GV2, ,GVk为为连通分支连通分支，图，图G的连通分支数记为的连通分支数记为 p(G)=k (k 1)；若若G连通，则连通，则p(G)= 1，若，若G非连通，则非连通，则p(G) 2，n阶零图的阶零图的连通分支最多，连通分支最多， p(Nn)= n25短程线与距离短程线与距离(3

24、) 短程线与距离短程线与距离 u与与v之间的之间的短程线短程线：u v，u与与v之间长度最短的通路之间长度最短的通路 u与与v之间的之间的距离距离：短程线的长度，记为：短程线的长度，记为d(u,v) d(u,v)的性质：的性质： d(u,v) 0, u,v不连通时不连通时d(u,v) = d(u,v)=d(v,u) d(u,v)+d(v,w) d(u,w) （三角不等式）（三角不等式）26图操作与图操作与割集割集1. 图操作图操作 G v 从从G中将中将v及关联的边去掉及关联的边去掉 G V 从从G中删除中删除V 中所有的顶点中所有的顶点 G e 将将e从从G中去掉中去掉 G E 删除删除E

25、中所有边中所有边 2. 点割集与边割集点割集与边割集定义定义14.15 G=, V V V 为为点割集点割集p(G V )p(G)且且V 有极小性有极小性(两个条件两个条件) v为为割点割点特殊的点割集特殊的点割集V =v定义定义14.16 G=, E E E 是是边割集边割集p(G E )p(G)且且E 有极小性有极小性(两个条件两个条件) e是是割边割边(桥桥)特殊的边割集特殊的边割集E =e27例题例题例例3 v1,v4,v5,v6是点是点割集，割集，v5,v6是割点。是割点。 v2,v5和和v1,v3,v4是点割是点割集吗？集吗？e1,e2, e1,e3,e5,e6, e8等等是边割集

26、，是边割集，e8是桥。是桥。e7,e9,e5,e6 是边割集吗？是边割集吗？几点说明：几点说明：l Kn中无点割集，中无点割集，Nn中既无点割集，也无边割集，其中中既无点割集，也无边割集，其中Nn为为 n 阶零图。图阶零图。图G的点的点(边边)割集可能有多个，不具有惟一性。割集可能有多个，不具有惟一性。l 若若G 连通，连通，E 为边割集，则为边割集，则 p(G E )=2，V 为点割集，则为点割集，则 p(G V ) 2 28点连通度与边连通度点连通度与边连通度定义定义14.17 设设G为为无向连通非完全图无向连通非完全图 点连通度点连通度 (G) = min |V | V 为点割集为点割集

27、 ，简称连通度，简称连通度 规定：规定： (Kn) = n 1， 非连通图非连通图G 的的 (G) = 0 若若 (G) k，则称，则称G为为 k-连通图连通图 定义定义14.18 设设G为为无向连通图无向连通图 边连通度边连通度 (G) = min |E | E 为边割集为边割集 规定：若规定：若G非连通，则非连通，则 (G) = 0 若若 (G) r，则称，则称G是是 r 边边-连通图连通图图中，图中， = =1，它是，它是 1-连通图连通图 和和 1边边-连通图连通图29几点说明几点说明l (Kn)= (Kn)=n 1l G非连通，则非连通，则 = =0l 若若G中有割点，则中有割点，则

28、 =1，若有桥，则，若有桥，则 =1l 若若 (G)=k, 则则G是是1-连通图，连通图，2-连通图，连通图，k-连通图，但连通图，但不是不是(k+s)-连通图，连通图，s 1l 若若 (G)=r, 则则G是是1边边-连通图，连通图，2边边-连通图，连通图，r边边-连通连通图，但不是图，但不是(r+s)边边-连通图，连通图，s 1l , , 之间的关系之间的关系.定理定理14.7 (G)(G)(G)30有向图的连通性有向图的连通性定义定义14.19 D=为有向图为有向图 vi 可达可达 vj（vi vj） 从从vi 到到vj 存在通路。规定：存在通路。规定：vi vi vi 与与vj 相互可达

29、相互可达（vi vj） vi vj 且且vj vi性质性质 具有自反性、传递性具有自反性、传递性 具有自反性、对称性、传递性具有自反性、对称性、传递性 定义定义14.20 D=为有向图为有向图vi 到到vj 的的短程线短程线 vi vj，从，从vi 到到vj长度最短的通路长度最短的通路vi 到到vj 的的距离距离 短程线的长度，记为短程线的长度，记为d定义与无向图类似，只需注意距离表示法的不同。定义与无向图类似，只需注意距离表示法的不同。无向图中无向图中d(vi,vj)，有向图中，有向图中d，因为，因为 d无对称性无对称性31有向图的连通性及分类有向图的连通性及分类定义定义14.21 D=为有

30、向图为有向图 D弱连通图弱连通图(连通图连通图)基图为连通图基图为连通图 D单向连通图单向连通图 vi,vj V，vivj 或或 vjvi 至少其一成立至少其一成立 D强连通图强连通图 vi,vj V，vivj易知，强连通易知，强连通单向连通单向连通弱连通弱连通判别法判别法定理定理14.8 D强连通当且仅当强连通当且仅当D中存在经过每个顶点至少一次中存在经过每个顶点至少一次的回路的回路定理定理14.9 D单向连通当且仅当单向连通当且仅当D中存在经过每个顶点至少一中存在经过每个顶点至少一次的通路。次的通路。32极大路径与扩大路径法极大路径与扩大路径法无向图中无向图中在在n 阶无向图阶无向图G=中

31、，设中，设 为为G中一条中一条路径路径，若，若 的的始始点和终点点和终点与与 外的顶点都不相邻，就称外的顶点都不相邻，就称 是一条是一条极大路径极大路径。对于对于G中的任意一条中的任意一条路径路径 l，若此路径的始点或终点与，若此路径的始点或终点与 l 外外的顶点相邻，就把这个路径延伸到新的顶点，继续这一过的顶点相邻，就把这个路径延伸到新的顶点，继续这一过程，直到最后不能向外延伸为止。最后总能得到一条极大路程，直到最后不能向外延伸为止。最后总能得到一条极大路径径 l+k（长度为（长度为 l 的路径扩大成了长度为的路径扩大成了长度为 l+k 的路径），称这的路径），称这种构造极大路径的方法为种构

32、造极大路径的方法为“扩大路径法扩大路径法”.有向图中类似讨论，只需注意，在每步扩大中保证有向边方有向图中类似讨论，只需注意，在每步扩大中保证有向边方向与通路方向的一致性。向与通路方向的一致性。33实例实例上图中，上图中，(1)中实线边所示的长为中实线边所示的长为2的初始路径的初始路径 ，(2),(3),(4)中实线边所示的都是它扩展成的极大路径中实线边所示的都是它扩展成的极大路径. 还能找到另外的极大路径吗？还能找到另外的极大路径吗？由某条路径扩大出的由某条路径扩大出的极大路径不惟一极大路径不惟一，极大路径不一定是，极大路径不一定是图中最长的路径图中最长的路径 (1) (2) (4) (3)3

33、4扩大路径法的应用扩大路径法的应用例例4 设设 G 为为 n（n 4）阶无向简单图，）阶无向简单图， 2，证明，证明G 中存在中存在长度长度 +1 的圈的圈.证证 不妨假设不妨假设G为连通图。任取两个顶点，它们之间一定存在为连通图。任取两个顶点，它们之间一定存在路径路径 0 。设。设 = v0v1vl 是由初始路径是由初始路径 0 用扩大路径法的得用扩大路径法的得到的极大路径，则到的极大路径，则 l （为什么？）（为什么？）. 因为因为v0 不与不与 外顶点相邻，又外顶点相邻，又 d(v0) ，因而在，因而在 上除上除 v1外，至少还存在外，至少还存在 1个顶点与个顶点与 v0 相邻相邻. 设

34、设 vt 是极大路径上离是极大路径上离 v0 最远的顶点，于是最远的顶点，于是 v0v1vtv0 为为 G 中长度中长度 +1 的圈的圈. 35二部图二部图定义定义14.23 设设 G=为一个无向图，若能将为一个无向图，若能将V 分成分成V1和和V2(V1 V2=V，V1 V2=)，使得，使得G 中的每条边的两个端点都是中的每条边的两个端点都是一个属于一个属于V1，另一个属于，另一个属于V2，则称，则称 G 为为二部图二部图 ( 或称或称二分二分图图、偶图偶图等等 )，称，称V1 和和V2 为为互补顶点子集互补顶点子集，常将二部图，常将二部图G记为记为. 又若又若G是简单二部图，是简单二部图，

35、V1中每个顶点均与中每个顶点均与V2中所有的顶点相中所有的顶点相邻，则称邻，则称G为为完全二部图完全二部图，记为，记为 Kr,s，其中，其中r=|V1|，s=|V2|. 注意，注意，n 阶零图为二部图阶零图为二部图. 36二部图的判别法二部图的判别法定理定理14.10 无向图无向图G=是是二部图二部图当且仅当当且仅当G中无奇圈。中无奇圈。例：由定理例：由定理14.10可知下图中各图都是二部图，哪些是完全二可知下图中各图都是二部图，哪些是完全二部图？哪些图是同构的？部图？哪些图是同构的？3714.4 图的矩阵表示图的矩阵表示无向图的关联矩阵（对图无限制）无向图的关联矩阵（对图无限制）定义定义14

36、.23 无向图无向图G=，|V|=n，|E|=m，令，令 mij为为 vi 与与 ej的关联次数，称的关联次数，称(mij)n m为为G 的的关联矩阵关联矩阵，记为，记为M(G). 性质性质平行边的列相同平行边的列相同)4(2)3(),.,2 , 1()()2(),.,2 , 1(2)1(,11mmnivdmmjmjiijimjijniij 38有向图的关联矩阵（有向图的关联矩阵（无环有向图无环有向图）定义定义14.24 有向图有向图D=，令，令则称则称 (mij)n m为为D的的关联矩阵关联矩阵，记为，记为M(D). 性质性质 平行边对应的列相同平行边对应的列相同)(,.,2 , 1),()

37、 1(),() 1()(),.,2 , 1(0)(111321mjmjiijiijniijnivdmvdmmjm 的的终终点点为为，不不关关联联与与，的的始始点点为为jijijiijevevevm10,1有向图的关联矩阵有向图的关联矩阵39有向图的邻接矩阵有向图的邻接矩阵定义定义14.25 设有向图设有向图D=, V=v1, v2, , vn, E=e1, e2, , em, 令令 为顶点为顶点 vi 邻接到顶点邻接到顶点 vj 边的条数，称边的条数，称 为为D的的邻接矩阵邻接矩阵，记作，记作A(D)，或简记为，或简记为A. (n n)性质性质 的回路数的回路数中长度为中长度为的通路数的通路数

38、中长度为中长度为1)4(1) 3(,.,2 , 1),()2(,.,2 , 1),() 1 (1)1(,)1(1)1(1)1(DaDmanjvdanivdaniiijiijjniijinjij)(1ijannija)()(140推论推论 设设Bl=A+A2+Al（l 1），则），则 Bl中元素之和中元素之和 为为D中长度小于或等于中长度小于或等于 l 的通路数的通路数. 为为D中长度为中长度为 l 的通路总数，的通路总数，)(lija)(liia ninjlija11)( niliia1)( ninjlijb11)( niliib1)(定理定理14.11 设设 A为有向图为有向图 D 的邻接矩

39、阵，的邻接矩阵，V=v1, v2, , vn为为顶点集，则顶点集，则 A 的的 l 次幂次幂 Al（l 1）中元素）中元素为为D中中vi 到到vj长度为长度为 l 的通路数，其中的通路数，其中为为vi到自身长度为到自身长度为 l 的回路数，而的回路数，而为为D中长度小于或等于中长度小于或等于 l 的回路数的回路数为为D 中长度为中长度为 l 的回路总数的回路总数. 邻接矩阵的应用邻接矩阵的应用41例例5 有向图有向图D如图所示，求如图所示，求 A, A2, A3, A4，并回答诸问题：，并回答诸问题：(1) D 中长度为中长度为1, 2, 3, 4的通路各有多少条？其中回路分别为多的通路各有多

40、少条？其中回路分别为多少条？少条？(2) D 中长度小于或等于中长度小于或等于4的通路为多少条？其中有多少条回路？的通路为多少条？其中有多少条回路？实例实例42 1004010410050001010310030104000110020102100300010101100101020001432AAAA(1) D中长度为中长度为1的通路为的通路为8条，其中有条，其中有1条是回路条是回路. D中长度为中长度为2的通路为的通路为11条，其中有条，其中有3条是回路条是回路. D中长度为中长度为3和和4的通路分别为的通路分别为14和和17条，回路分别为条，回路分别为1与与3条条.(2) D中长度小于等

41、于中长度小于等于4的通路为的通路为50条，其中有条，其中有8条是回路条是回路.实例求解实例求解43否否则则可可达达,01jivvijp 1101110111110001P定义定义14.26 设设D=为有向图为有向图. V=v1, v2, , vn, 令令 称称 (pij)n n 为为D的可达矩阵，记作的可达矩阵，记作P(D)，简记为，简记为P. (n n)由于由于 vi V，vi vi，所以，所以P(D)主对角线上的元素全为主对角线上的元素全为1. 由定义不难看出由定义不难看出, D 强连通当且仅当强连通当且仅当 P(D)为全为全1矩阵矩阵. 下图所示有向图下图所示有向图 D 的可达矩阵为的可

42、达矩阵为有向图的可达矩阵有向图的可达矩阵44第十四章第十四章 习题课习题课主要内容主要内容l 无向图、有向图、关联与相邻、简单图、完全图、正则图、无向图、有向图、关联与相邻、简单图、完全图、正则图、子图、补图；握手定理与推论；图的同构子图、补图；握手定理与推论；图的同构l 通路与回路及其分类通路与回路及其分类l 无向图的连通性与连通度无向图的连通性与连通度l 有向图的连通性及其分类有向图的连通性及其分类l 图的矩阵表示图的矩阵表示45基本要求基本要求l 深刻理解握手定理及推论的内容并能灵活地应用它们深刻理解握手定理及推论的内容并能灵活地应用它们l 深刻理解图同构、简单图、完全图、正则图、子图、

43、补图、深刻理解图同构、简单图、完全图、正则图、子图、补图、二部图的概念以及它们的性质及相互之间的关系二部图的概念以及它们的性质及相互之间的关系l 记住通路与回路的定义、分类及表示法记住通路与回路的定义、分类及表示法l 深刻理解与无向图连通性、连通度有关的诸多概念深刻理解与无向图连通性、连通度有关的诸多概念l 会判别有向图连通性的类型会判别有向图连通性的类型l 熟练掌握用邻接矩阵及其幂求有向图中通路与回路数的方熟练掌握用邻接矩阵及其幂求有向图中通路与回路数的方法，会求可达矩阵法，会求可达矩阵 4619阶无向图阶无向图G中，每个顶点的度数不是中，每个顶点的度数不是5就是就是6. 证明证明G中至少有

44、中至少有5个个6度顶点或至少有度顶点或至少有6个个5度顶点度顶点. 练习练习1证证 关键是利用握手定理的推论关键是利用握手定理的推论. 方法一：穷举法方法一：穷举法设设G中有中有x个个5度顶点，则必有度顶点，则必有(9 x)个个6度顶点，由握手定度顶点，由握手定理推论可知，理推论可知，(x,9 x)只有只有5种可能：种可能：(0,9), (2,7), (4,5), (6,3), (8,1）它们都满足要求）它们都满足要求. 方法二：反证法方法二：反证法否则，由握手定理推论可知，否则，由握手定理推论可知，“G至多有至多有4个个5度顶点并且度顶点并且至多有至多有4个个6度顶点度顶点”，这与，这与G是

45、是 9 阶图矛盾阶图矛盾. 472数组数组2, 2, 2, 2, 3, 3能简单图化吗？若能，画出尽可能多的能简单图化吗？若能，画出尽可能多的非同构的图来非同构的图来. 练习练习2只要能画出只要能画出6 阶无向简单图，就说明它可简单图化阶无向简单图，就说明它可简单图化. 下图的下图的4个图都以此数列为度数列，请证明它们彼此不同构，都是个图都以此数列为度数列，请证明它们彼此不同构，都是K6的子图的子图.48用扩大路径法证明用扩大路径法证明.情况一：情况一： +. 证明证明D中存在长度中存在长度 +1的圈的圈. 设设 = v0v1vl为极大路径，则为极大路径，则l (为什么为什么?).由于由于d

46、(v0) ，所以在所以在 上存在上存在PLAYiiivvv,.,21010.21vvvvvviii邻接到v0，于是情况二：情况二： + ，只需注意，只需注意d+(vl) + .3设设D=为有向简单图，已知为有向简单图，已知 (D) 2， +(D)0，(D)0，证明，证明D中存在长度中存在长度 max +,+1的圈的圈.为为D中长度中长度 +1的有向圈的有向圈练习练习349(1) D中有几种非同构的圈？中有几种非同构的圈？(2) D中有几种非圈非同构的简单回路？中有几种非圈非同构的简单回路？(3) D是哪类连通图是哪类连通图?(4) D中中v1到到v4长度为长度为1,2,3,4的通路各多少的通路

47、各多少 条？其中几条是非初级的简单通路？条？其中几条是非初级的简单通路？(5) D中中v1到到v1长度为长度为1,2,3,4的回路各多少的回路各多少 条？讨论它们的类型条？讨论它们的类型.(6) D中长度为中长度为4的通路（不含回路）有多少条？的通路（不含回路）有多少条？(7) D中长度为中长度为4的回路有多少条？的回路有多少条？(8) D中长度中长度 4的通路有多少条？其中有几条是回路？的通路有多少条？其中有几条是回路？(9) 写出写出D的可达矩阵的可达矩阵. 4有向图有向图D如图所示，如图所示，回答下列诸问：回答下列诸问：练习练习450解答解答(1) D中有中有3种非同构的圈，长度分别为种

48、非同构的圈，长度分别为1,2,3，请画出它们的，请画出它们的图形图形.(2) D中有中有3种非圈的非同构的简单回路，它们的长度分别为种非圈的非同构的简单回路，它们的长度分别为 4,5,6. 请画出它们的图形来请画出它们的图形来.(3) D是强连通的（为什么？）是强连通的（为什么？）为解为解(4)(8)，只需先求，只需先求D的邻接矩阵的前的邻接矩阵的前4次幂次幂. 1222234412222465012112220121222310010121100102210100100101000021432AAAA51(4) v1到到v4长度为长度为1,2,3,4的通路数分别为的通路数分别为0,0,2,2

49、. 其中只有其中只有长度为长度为4的两条是非初级的简单通路（定义意义下），见的两条是非初级的简单通路（定义意义下），见下图所示下图所示. 解答解答52解答解答(5) v1到到v1长度为长度为1,2,3,4的回路数分别为的回路数分别为1,1,3,5. 其中长度为其中长度为1的是初级的的是初级的(环环)；长度为；长度为2的是复杂的；长度为的是复杂的；长度为3的中有的中有1条条是复杂的，是复杂的，2条是初级的；长度为条是初级的；长度为4的有的有1条是复杂的，有条是复杂的，有4条是非初级的简单回路条是非初级的简单回路. 请在图中行遍以上各回路请在图中行遍以上各回路.(6) 长度为长度为4的通路的通路(

50、不含回路不含回路)为为33条条.(7) 长度为长度为4的回路为的回路为11条条. (8) 长度长度 4的通路的通路88条，其中条，其中22条为回路条为回路. (9) 4 4的全的全1矩阵矩阵. 53极大路径与扩大路径法极大路径与扩大路径法无向图中无向图中设设G=为为 n 阶无向图，阶无向图，E. 设设 l 为为G中一条路径，若中一条路径，若此路径的始点或终点与通路外的顶点相邻，就将它们扩到通此路径的始点或终点与通路外的顶点相邻，就将它们扩到通路中来，继续这一过程，直到最后得到的通路的两个端点不路中来，继续这一过程，直到最后得到的通路的两个端点不与通路外的顶点相邻为止与通路外的顶点相邻为止. 设