离散数学(第十四章)剖析课件

114.3 图的连通性图的连通性无向图的连通性无向图的连通性(1)顶点之间的连通关系：顶点之间的连通关系：G=为无向图为无向图 若若 vi 与与 vj 之间有通路，则之间有通路，则 vi vj 是是V上的等价关系上的等价关系 R=|u,v V且且u v(2)G的连通性与连通分支的连通性与连通分支 若若 u,v V，u v，则称，则称G连通连通 V/R=V1,V2,Vk，称，称GV1,GV2,GVk为为连通分连通分 支支，其个数，其个数 p(G)=k (k 1)；k=1，G连通连通2短程线与距离短程线与距离(3)短程线与距离短程线与距离 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)3无向图的连通度无向图的连通度1.删除顶点及删除边删除顶点及删除边 G v 从从G中将中将v及关联的边去掉及关联的边去掉 G V 从从G中删除中删除V 中所有的顶点中所有的顶点 G e 将将e从从G中去掉中去掉 G E 删除删除E 中所有边中所有边 2.点割集与边割集点割集与边割集 点割集与割点点割集与割点定义定义14.16 G=,VV V 为为点割集点割集p(G V)p(G)且有极小性且有极小性 v为为割点割点v为点割集为点割集定义定义14.17 G=,EE E 是是边割集边割集p(G E)p(G)且有极小性且有极小性 e是是割边割边（桥）（桥）e为边割集为边割集4点割集与割点点割集与割点例例3 v1,v4，v6是点是点割集，割集，v6是割点是割点.v2,v5是点割集吗？是点割集吗？e1,e2，e1,e3,e5,e6，e8等是边割集，等是边割集，e8是是桥，桥，e7,e9,e5,e6 是边割是边割集吗？集吗？几点说明：几点说明：lKn中无点割集，中无点割集，Nn中既无点割集，也无边割集，其中中既无点割集，也无边割集，其中Nn为为 n 阶零图阶零图.l若若G 连通，连通，E 为边割集，则为边割集，则 p(G E)=2，V 为点割集，为点割集，则则 p(G V)2 5点连通度与边连通度点连通度与边连通度定义定义14.18 G为连通非完全图为连通非完全图 点连通度点连通度 (G)=min|V|V 为点割集为点割集 规定规定 (Kn)=n 1 若若G非连通，非连通，(G)=0 若若 (G)k，则称，则称G为为 k-连通图连通图 定义定义14.19 设设G为连通图为连通图 边连通度边连通度(G)=min|E|E 为边割集为边割集 若若G非连通，则非连通，则(G)=0 若若(G)r，则称，则称G是是 r 边边-连通图连通图图中，图中，=1，它是，它是 1-连通图连通图 和和 1边边-连通图连通图6几点说明几点说明l(Kn)=(Kn)=n 1lG非连通，则非连通，则 =0l若若G中有割点，则中有割点，则=1，若有桥，则，若有桥，则=1l若若(G)=k,则则G是是1-连通图，连通图，2-连通图，连通图，k-连通图，但连通图，但不是不是(k+s)-连通图，连通图，s 1l若若(G)=r,则则G是是1-边连通图，边连通图，2-边连通图，边连通图，r-边连通边连通图，但不是图，但不是(r+s)-边连通图，边连通图，s 1l,之间的关系之间的关系.定理定理7.5 (G)(G)(G)请画出一个请画出一个 的无向简单图的无向简单图7有向图的连通性有向图的连通性定义定义14.20 D=为有向图为有向图 vi vj（vi 可达可达 vj）vi 到到vj 有通路有通路 vi vj（vi 与与vj 相互可达）相互可达）性质性质 具有自反性具有自反性(vi vi)、传递性、传递性 具有自反性、对称性、传递性具有自反性、对称性、传递性 vi 到到vj 的短程线与距离的短程线与距离类似于无向图中，只需注意距离表示法的不同类似于无向图中，只需注意距离表示法的不同(无向图中无向图中d(vi,vj)，有向图中，有向图中d)及及 d无对称性无对称性8有向图的连通性及分类有向图的连通性及分类定义定义14.22 D=为有向图为有向图 D弱连通弱连通(连通连通)基图为无向连通图基图为无向连通图 D单向连通单向连通 vi,vj V，vivj 或或 vjvi D强连通强连通 vi,vj V，vivj易知，强连通易知，强连通单向连通单向连通弱连通弱连通判别法判别法定理定理14.8 D强连通当且仅当强连通当且仅当D中存在经过每个顶点至少一次中存在经过每个顶点至少一次的回路的回路定理定理14.9 D单向连通当且仅当单向连通当且仅当D中存在经过每个顶点至少一中存在经过每个顶点至少一次的通路次的通路实例实例 强连通强连通单连通单连通弱连通弱连通10二部图二部图定义定义14.23 设设 G=为一个无向图，若能将为一个无向图，若能将 V分成分成 V1和和V2(V1 V2=V，V1 V2=)，使得，使得 G 中的每条边的两个端点都是中的每条边的两个端点都是一个属于一个属于V1，另一个属于，另一个属于V2，则称，则称 G 为为二部图二部图(或称或称二分二分图图、偶图偶图等等)，称，称V1和和V2为为互补顶点子集互补顶点子集，常将二部图，常将二部图G记为记为.又若又若G是简单二部图，是简单二部图，V1中每个顶点均与中每个顶点均与V2中所有的顶点相中所有的顶点相邻，则称邻，则称G为为完全二部图完全二部图，记为，记为 Kr,s，其中，其中r=|V1|，s=|V2|.注意，注意，n 阶零图为二部图阶零图为二部图.11K K2,2,3 3K K3,3,3 3一个无向图一个无向图G=是二部图当且仅是二部图当且仅当当G中无奇数长度的回路。中无奇数长度的回路。若若若若|V V1 1|=n n，|V V2 2|=mm，则记完全二部图，则记完全二部图，则记完全二部图，则记完全二部图G G为为为为K Kn n,m m圈的长度都是偶数圈的长度都是偶数12例例例例1 1：判断下列图是否为二部图。：判断下列图是否为二部图。：判断下列图是否为二部图。：判断下列图是否为二部图。v v4 4v v3 3v v2 2v v1 1v v5 5v v6 6v v7 7v v8 8同构于同构于同构于同构于v v4 4v v3 3v v2 2v v1 1v v5 5v v6 6同构于同构于同构于同构于v v6 6v v4 4v v3 3v v2 2v v1 1v v5 5v v7 7v v8 8v v4 4v v3 3v v2 2v v1 1v v5 5v v6 61314.4 图的矩阵表示图的矩阵表示无向图的关联矩阵（对图无限制）无向图的关联矩阵（对图无限制）定义定义14.24 无向图无向图G=，|V|=n，|E|=m，令，令 mij为为 vi 与与 ej的关联次数，称的关联次数，称(mij)n m为为G 的的关联矩阵关联矩阵，记为，记为M(G).mij 的的可能取值为可能取值为0,1,2.性质性质无向图的关联矩阵无向图的关联矩阵例如例如e1e2e3e4e5e6v5v1v2v3v4M(G)=2 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 15有向图的关联矩阵（无环有向图）定义定义14.25 有向有向图D=，令，令则称则称(mij)n m为为D的的关联矩阵关联矩阵，记为，记为M(D).(4)平行边对应的列相同平行边对应的列相同性质性质有向图的关联矩阵实例实例v1v2v3v4e2e1e3e4e5e6e7M(D)=-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 017有向图的邻接矩阵（无限制）有向图的邻接矩阵（无限制）定义定义14.26 设有向图设有向图D=,V=v1,v2,vn,E=e1,e2,em,令为顶点令为顶点 vi 邻接到顶点邻接到顶点 vj 边的条数，称为边的条数，称为D的的邻接矩邻接矩阵阵，记作，记作A(D)，或简记为，或简记为A.性质性质 18推推论 设Bl=A+A2+Al（l 1），），则 Bl中元素中元素为D中长度为 l 的通路总数，定理定理14.11 设 A为有向有向图 D 的的邻接矩接矩阵，V=v1,v2,vn为顶点集，点集，则 A 的的 l 次次幂 Al（l 1）中元素）中元素为D中vi 到vj长度为 l 的通路数，其中为vi到自身长度为 l 的回路数，而为D中中长度小于或等于度小于或等于 l 的回路数的回路数为D中中长度小于或等于度小于或等于 l 的通路数的通路数.邻接矩阵的应用邻接矩阵的应用为为D 中长度为中长度为 l 的回路总数的回路总数.19例例5 有向图有向图D如图所示，求如图所示，求 A,A2,A3,A4，并回答诸问题：，并回答诸问题：(1)D 中长度为中长度为1,2,3,4的通路各有多少条？其中回路分别为多的通路各有多少条？其中回路分别为多少条？少条？(2)D 中长度小于或等于中长度小于或等于4的通路为多少条？其中有多少条回路的通路为多少条？其中有多少条回路？实例实例20(1)D中中长度度为1的通路的通路为8条，其中有条，其中有1条是回路条是回路.D中中长度度为2的通路的通路为11条，其中有条，其中有3条是回路条是回路.D中长度为中长度为3和和4的通路分别为的通路分别为14和和17条，回路分别条，回路分别 为为1与与3条条.(2)D中长度小于等于中长度小于等于4的通路为的通路为50条，其中有条，其中有8条是回路条是回路.实例求解实例求解21定定义14.27 设D=为有向有向图.V=v1,v2,vn,令令 有向图的可达矩阵（无限制）有向图的可达矩阵（无限制）称称(pij)n n 为为D的可达矩阵，记作的可达矩阵，记作P(D)，简记为，简记为P.由于由于 vi V，vivi，所以，所以P(D)主对角线上的元素全为主对角线上的元素全为1.由定义不难看出由定义不难看出,D 强连通当且仅当强连通当且仅当 P(D)为全为全1矩阵矩阵.下图所示有向图下图所示有向图 D 的可达矩阵为的可达矩阵为2、边不相交的、边不相交的G1=G2=同为无向图或同为有向图同为无向图或同为有向图G1与与G2是不相交的是不相交的E1E2=V1V2=G1与与G2是边不相交是边不相交E1E2=4、图的交、图的交G1=G2=是可运算的是可运算的V1V2为结点集为结点集E1E2为边集合为边集合G1和和G2的交的交G1G25、图的并、图的并G1=G2=是可运算的是可运算的V1 V2为结点集为结点集E1 E2为边集合为边集合G1和和G2的并的并G1 G26、图的差、图的差G1=G2=是可运算的是可运算的G1与与G2的差的差:在在G1中去掉中去掉G2的边所得到的图的边所得到的图G1-G27、图的环和、图的环和G1=G2=是可运算的是可运算的V1 V2为结点集为结点集E1 E2为边集合为边集合G1和和G2的环和的环和G1 G2图运算的举例图运算的举例与如下图所示，求：与如下图所示，求：G G1 1G G2 2 G G1 1G G2 2 G G1 1-G-G2 2 G G2 2-G-G1 1，G G1 1G G2 2 。G G1 1G G2 2V V1 1V V2 2E1 1E2 2=a,b,d=e1 1,e2 2,e5 5G G1 1G G2 2V V1 1V V2 2e1 1,e2 2,e3 3,e4 4,e5 5,e6 6,e7 7,e8 8,e9 9,e1010=a,b,c,d,eE1 1 E2 2=G G1 1-G-G2 2G G2 2 G G1 1G G1 1G G2 2E E1 1 E E2 2=V V1 1V V2 2=a,b,c,d,ee3 3,e4 4,e6 6,e7 7,e8 8,e9 9,e101033第十四章第十四章 习题课习题课主要内容主要内容l无向图、有向图、关联与相邻、简单图、完全图、正则图、无向图、有向图、关联与相邻、简单图、完全图、正则图、子图、补图；握手定理与推论；图的同构子图、补图；握手定理与推论；图的同构l通路与回路及其分类通路与回路及其分类l无向图的连通性与连通度无向图的连通性与连通度l有向图的连通性及其分类有向图的连通性及其分类l图的矩阵表示图的矩阵表示34基本要求基本要求l深刻理解握手定理及推论的内容并能灵活地应用它们深刻理解握手定理及推论的内容并能灵活地应用它们l深刻理解图同构、简单图、完全图、正则图、子图、补图、深刻理解图同构、简单图、完全图、正则图、子图、补图、二部图的概念以及它们的性质及相互之间的关系二部图的概念以及它们的性质及相互之间的关系l记住通路与回路的定义、分类及表示法记住通路与回路的定义、分类及表示法l深刻理解与无向图连通性、连通度有关的诸多概念深刻理解与无向图连通性、连通度有关的诸多概念l会判别有向图连通性的类型会判别有向图连通性的类型l熟练掌握用邻接矩阵及其幂求有向图中通路与回路数的方熟练掌握用邻接矩阵及其幂求有向图中通路与回路数的方法，会求可达矩阵法，会求可达矩阵 3519阶无向图阶无向图G中，每个顶点的度数不是中，每个顶点的度数不是5就是就是6.证明证明G中至少有中至少有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是是 9 阶图矛盾阶图矛盾.362数组数组2,2,2,2,3,3能简单图化吗？若能，画出尽可能多的能简单图化吗？若能，画出尽可能多的非同构的图来非同构的图来.练习练习2只要能画出只要能画出6 阶无向简单图，就说明它可简单图化阶无向简单图，就说明它可简单图化.下图的下图的4个图都以此数列为度数列，都是个图都以此数列为度数列，都是K6的子图的子图.37用扩大路径法证明用扩大路径法证明.情况一：情况一：+.证明证明D中存在长度中存在长度 +1的圈的圈.设设 =v0v1vl为极大路径，则为极大路径，则l (为什么为什么?).由于由于d(v0)，所以在所以在 上存在上存在PLAY邻接到v0，于是情况二：情况二：+，只需注意，只需注意d+(vl)+.3设设D=为有向简单图，已知为有向简单图，已知 (D)2，+(D)0，(D)0，证明，证明D中存在长度中存在长度 max+,+1的圈的圈.为为D中长度中长度 +1的有向圈的有向圈练习练习338(1)D中有几种非同构的圈？中有几种非同构的圈？(2)D中有几种非圈非同构的简单回路？中有几种非圈非同构的简单回路？(3)D是哪类连通图是哪类连通图?(4)D中中v1到到v4长度为长度为1,2,3,4的通路各多少的通路各多少 条？其中几条是非初级的简单通路？条？其中几条是非初级的简单通路？(5)D中中v1到到v1长度为长度为1,2,3,4的回路各多少的回路各多少 条？讨论它们的类型条？讨论它们的类型.(6)D中长度为中长度为4的通路（不含回路）有多少条？的通路（不含回路）有多少条？(7)D中长度为中长度为4的回路有多少条？的回路有多少条？(8)D中长度中长度 4的通路有多少条？其中有几条是回路？的通路有多少条？其中有几条是回路？(9)写出写出D的可达矩阵的可达矩阵.4有向图有向图D如图所示，如图所示，回答下列诸问：回答下列诸问：练习练习439解答解答(1)D中有中有3种非同构的圈，长度分别为种非同构的圈，长度分别为1,2,3，请画出它们的，请画出它们的图形图形.(2)D中有中有3种非圈的非同构的简单回路，它们的长度分别为种非圈的非同构的简单回路，它们的长度分别为 4,5,6.请画出它们的图形来请画出它们的图形来.(3)D是强连通的（为什么？）是强连通的（为什么？）为解为解(4)(8)，只需先求，只需先求D的邻接矩阵的前的邻接矩阵的前4次幂次幂.40(4)v1到到v4长度为长度为1,2,3,4的通路数分别为的通路数分别为0,0,2,2.其中只有其中只有长度为长度为4的两条是非初级的简单通路（定义意义下），见的两条是非初级的简单通路（定义意义下），见下图所示下图所示.解答解答41解答解答(5)v1到到v1长度为长度为1,2,3,4的回路数分别为的回路数分别为1,1,3,5.其中长度为其中长度为1的是初级的的是初级的(环环)；长度为；长度为2的是复杂的；长度为的是复杂的；长度为3的中有的中有1条条是复杂的，是复杂的，2条是初级的；长度为条是初级的；长度为4的有的有1条是复杂的，有条是复杂的，有4条是非初级的简单回路条是非初级的简单回路.请在图中行遍以上各回路请在图中行遍以上各回路.(6)长度为长度为4的通路的通路(不含回路不含回路)为为33条条.(7)长度为长度为4的回路为的回路为11条条.(8)长度长度 4的通路的通路88条，其中条，其中22条为回路条为回路.(9)4 4的全的全1矩阵矩阵.