第8章图论基础.ppt

1、第8章 图论基础,第1节 图的基本概念 第2节 子图与图的运算 第3节 路径、回路和连通性 第4节 图的矩阵表示,第1节 图的基本概念,1、图的定义 2、无向图、有向图、混合图 3、邻接结点、邻接边 4、自环、平行边、简单图 5、度（入度、出度） 6、奇结点、偶结点 7、孤立结点、端点（悬挂点）、悬挂边 8、零图、平凡图、d度正则图、完全图、赋权图 9、图同构10、判断两个图同构的必要条件 11、子图、真子图、生成子图、补图,1、图的定义(图的三元组表示),图G是一个三元组:,G=,G,V(G),E(G),非空结点集合,边的集合,从E(G)到结点无序偶对（或有序偶对）的映射,举例,G= V(G

2、)=a, b, c, d E(G)=e1 , e2, e3 , e4 , e5 , e6 G(e1)=(a,b)，G (e2)=(a,c) G (e3)=(b,d), G (e4)=(b,c) G (e5)=(d,c) ，G (e6)=(a,d) 请画出对应的无向图。,a,b,d,c,e1,e2,e3,e4,e5,e6,a,b,d,c,e1,e2,e3,e4,e5,e6,1、图的定义(图的二元组表示),图G是个二元组：G= ,非空结点集合,边的集合,举例,G= V=a, b, c, d E=(a, b), (a, c), (b, d), (b, c), , ,a,b,d,c,有向边,无向边,2

3、、无向图、有向图、混合图,（1）有向图：若图G中所有的边都是有向边。 （2）无向图：若图G中所有的边都是无向边。 （3）混合图：若图G中一些边是有向边，另一些边是 无向边。,只讨论有向图和无向图,3、邻接结点、邻接边,关联同一个结点的两条不同的边,邻接结点:,由一条边相连接的两个结点,邻接边:,邻接结点、邻接边举例,a、b、c、d 4个结点中的任意两个结点都是邻接结点； e1和e5不邻接； e4和e6不邻接； e2和e3不邻接。,4、自环、平行边、简单图,图G=,(1) 自 环:,关联于同一个结点的边,(2) 平行边:,关联于同一对结点的两条边,(3) 简单图:,无平行边和自环的图,多重边图,

4、平行边举例,在有向图中，如果边e1和e2关联于同一对结点，但方向相反，则它们不是平行边。,具有平行边的图，称为多重边图,5、度（入度、出度）,图: G=,vV,与结点v相关联的边的数目,(1) v的度:,G是无向图:,deg(v),(2) v的出度:,G是有向图:,以v为起点的边的条数,deg+(v),(3) v的入度:,以v为终点的边的条数,deg-(v),deg(v)= deg+(v)+deg-(v),自环的度,对于无向图中的一个自环，给该结点的度增加2； 对于有向图中的自环，给该结点增加一个出度和一个入度，故该结点的度也增加2。,结点度的举例,给出图1各结点的度； 给出图2各结点的出度、

5、入度、度。,解答,deg(v1)=deg(v4)=3 deg(v2)=deg(v3)=2,deg+(v1)=1, deg-(v1)=1, deg(v1)=2 deg+(v2)=1, deg-(v2)=2, deg(v2)=3 deg+(v3)=2, deg-(v3)=0, deg(v3)=2 deg+(v4)=2, deg-(v4)=1, deg(v4)=3 deg+(v5)=0, deg-(v5)=2, deg(v5)=2,(n,m)图,图,n个结点,m条边,(n, m) 图,定理(握手定理),(n, m)图,所有结点的度之和等于边数的两倍,证明, 每条边必关联两个结点 一条边给它所关联的两

6、个结点的度各增加1 为整个图的度数增加2, m条边则度增加2m, 结点的度数总和恰好为边数的两倍。,定理验证,m=5 deg(v1)+deg(v2)+deg(v3)+deg(v4) =3+2+2+3=10=2m,定理,(n, m)有向图,所有结点的出度之和等于入度之和等于边数,定理验证,m=6 deg+(v1)+ deg+(v2)+ deg+(v3) +deg+(v4)+ deg+(v5) =1+1+2+2+0=m deg-(v1)+ deg-(v2)+ deg-(v3) +deg-(v4)+ deg-(v5) =1+2+0+1+2=m,6、奇结点、偶结点,偶结点：,奇结点：,度数为奇数的结点

7、,度数为偶数的结点,定理,在任何图中，必有偶数个奇结点。 (在任何一个图G中，奇结点的个数必为偶数个),证明,图G=,|E|=m,V1:,V2:,V中奇结点集合,V中偶结点集合,偶结点的度数之和,偶数,偶数,奇结点的度数之和,偶数,|V1|,偶数,偶数个奇结点,7、孤立结点、悬挂点(端点)、悬挂边,图G=,vV,(1) 孤立结点:,deg(v)=0,(2) 悬挂点:,deg(v)=1,(3) 悬挂边:,与悬挂点关联的边,孤立结点、悬挂点、悬挂边举例,V5 是悬挂点； (v4, v5)是悬挂边; V6 是孤立结点,8、零图、平凡图、d度正则图、完全图、赋权图,G=:,简单无向图,（1）零图:,E

8、=,(n, 0) 图,（2）平凡图:,|V|=1,E=,(1, 0) 图,（3）d度正则图:,每个结点的度均为d,（4）完全图：,任意两点间恰有一条边连接,Kn,8、零图、平凡图、d度正则图、完全图、赋权图,(5) 赋权图：如果图G的每条边(vi, vj)或都标有一个数字lij，则称G为赋权图(加权图)。 边上所标的数字lij称为该边上的权；各条边上所有的权和称为该图的权。,举例,举例,2.5,1.6,3.0,3.5,无向赋权图,2.5,1.6,3.0,3.5,有向赋权图,9、图同构,两个图,G=,G=,双射函数g：,V V,v iV,g(vi)= vi ,(g(vi), g(vj) ) E,

9、（1）无向图:,(vi, vj)E,（2）有向图:,E,E,G与G同构,解释,（1）无向图:,双射函数g:VV:,保持结点间的邻接关系,（2）有向图:,双射函数g:VV:,保持结点间的邻接关系,保持边的方向一致,无向图同构举例,证明下面两个无向图同构。,证明,双射函数g: V V:,g(vi)=vi( i=1, 2, 3, 4, 5, 6 ),(v1,v4)E,(v1, v4)E,(v1,v5)E,(v1, v5)E,(v1,v6)E,(v1, v6)E,(v2,v4)E,(v2, v4)E,(v2,v5)E,(v2, v5)E,(v2,v6)E,(v2, v6)E,(v3,v4)E,(v3,

10、 v4)E,(v3,v5)E,(v3, v5)E,(v3,v6)E,(v3, v6)E,有向图同构举例,证明下面两个有向图同构。,证明,双射函数g:V V:,g(i) = vi (i=1, 2, 3, 4),E,E,E,E,E,E,E,E,10、判断两个图同构的必要条件,（1）结点数相同； （2）边数相同； （3）度数相同的结点数相同。,第2节 子图与图的运算,一、子图 二、图的运算(简介),一、子图,1、子图 2、真子图 3、生成子图 4、结点导出子图 5、边导出子图,1、子图,两个图,G=,G=,V V,E E,G是G的子图,2、真子图,两个图,G=,G=,V V,E E,G是G的真子图,

11、3、生成子图,两个图,G = ,G = ,V = V,E E,G是G的生成子图,子图的举例,4、结点导出子图,G=,VV,V ,以V为结点集合,起点和终点均在V 中的边的全体为边集合,由V导出的G的子图,GV,V V,导出子图GV-V,G - V,结点的导出子图举例,V= a, b, c, d, e 求: (1) 由导出子图 Ga, b, d, e (2) G - a, d,解答,5、边导出子图(略),G=,E E,E,V=v |,vV,(e)( eE,v与e关联) ,以V为结点集合,以E为边集,由E导出的子图,边导出子图举例,E=e1, e2, e3, e4, e5, e6 ,e7, e8

12、求: Ge1,e2,e5,e7 ,解答,二、图的运算（简介）,1、可运算的 2、边不相交的 3、点不相交的 4、图的交 5、图的并,6、图的差 7、图的环和 8、相对于图G的补图 9、相对于完全图的补图,1、可运算的,G1=,G2=,同为无向图或同为有向图,对任意的eE1E2,1(e)=2(e),G1与G2是可运算的,2、边不相交的,G1=,G2=,同为无向图或同为有向图,G1与G2是不相交的,E1E2 = ,V1V2 =,G1与G2是边不相交的,E1E2 = ,3、点不相交的,G1与G2是点不相交的,G1=,G2=,同为无向图或同为有向图,V1V2 =,可运算的举例,问： G1和G2是否是可

13、运算的？,解答,E1E2 =, e1, e2, e5 ,1(e1)=,(a,b),2(e1)=,(a,b),1(e2)=,(a,d),2(e2)=,(a,d),1(e5)=,(b,d),2(e5)=,(b,d),G1和G2是可运算的,4、图的交,G1=,G2=,是可运算的,V1V2为结点集,E1E2为边集合,G1和G2的交,G1G2,5、图的并,G1=,G2=,是可运算的,V1 V2为结点集,E1 E2为边集合,G1和G2的并,G1 G2,6、图的差,G1=,G2=,是可运算的,G1与G2的差:,在G1中去掉G2的边所得到的图,G1 - G2,7、图的环和,G1=,G2=,是可运算的,V1 V

14、2为结点集,E1 E2为边集合,G1和G2的环和,G1 G2,图运算的举例,与如下图所示，求： G1G2 G1G2 G1 - G2 G2 - G1 ， G1G2 。,G1G2,V1V2,E1E2,=a, b, d,= e1, e2, e5,G1G2,V1V2,e1, e2, e3, e4, e5, e6, e7, e8, e9, e10 ,=a,b,c,d,e,E1E2 =,G1 -G2,G2 G1,G1G2,E1 E2 =,V1V2,= a, b, c, d, e, e3, e4, e6, e7, e8, e9, e10 ,8、相对于图G的补图,G=的子图,G=是,给定另一个图G=,（1）E

15、 E - E,（2）V是E中的边所关联的结点集合,G是子图G的相对于图G的补图,解释,(1) EE (2) EE E (3) V 仅是E 中的边所关联的结点集合，不包含别的结点。 G G G (4) G与G的关系不是互逆的。,相对补图举例,图G和图G 如下图所示:,求图G 相对于图G的补图。,解答,E,E - E=,(a,e),(c,e),(d,e),V a, c, d, e ,图G 相对于图G的补图为G,G相对于图G的补图为G,不是G,没有结点e,9、相对于完全图的补图,补图是互逆的,给定一个图G, G中所有结点能使G成为完全图所添加的边,图G相对于完全图的补图,G的补图,补图举例,求G1和

16、G2的补图。,解答,解答,第3节 路径、回路和连通性,一、路径与回路 二、连通性,(1)路径,路径是结点和边的交替序列,图G=,v0,v1vnV,e1,e2enE,ei:关联vi-1和vi,序列v0e1v1e2envn :,从v0到vn的路径(或路),路径的起点,路径的终点,路径的长度:,路径中边的数目,(2)回路,起点和终点为同一个结点的路径回路,(3)简单路径、基本路径,简单路径:,简单回路:,基本路径:,基本回路:,边不重复的路径,边不重复的回路,点不重复的路径,点不重复的回路,路径举例,(1) AaAcBgChF:,(2)AbDdEeBfChF:,(3)AbDdEeBcA:,从A到F的

17、路径,长度为4,简单路径,不是基本路径,从A到F的路径,长度为5,简单路径,基本路径,从A到A的回路,长度为4,简单回路,基本回路,路径举例,v1e2v2e3v3e4v4,v4e1v1e2v2e3v3e4v4e1v1,简单路径,基本路径,不是基本路径,不是简单路径,定理,寻找基本路径的方法：,v和v是图G中的结点,存在从v到v的路径,存在从v到v的基本路径,从路径中去掉所有的回路,证明,从v到v存在路径P vv :,v0e1v1e2elvl,v,v,若Pvv不是基本路径,结点vi在该路径中不止一次出现,v0e1v1e2eivi ei+1 ejvjej+1elvl,vi=vj,在该路径中去掉从v

18、i到vj的边,v0e1v1e2eiviej+1elvl,从v0到vl的路径,如此反复去掉所有的回路,从v0到vl的基本路径,定理应用举例,(1) ae2be10de9ae2be4c,(2) ae1ae2be4c,是从a到c的一条路径,是从a到c的一条路径,解答,(1) ae2be10de9ae2be4c:,不是基本路径,去掉回路ae2be10de9a,ae2be4c,基本路径,(2)ae1ae2be4c:,不是基本路径,去掉回路ae1a,ae2be4c,基本路径,定理,n阶图中的基本路径的长度小于n。,证明,基本路径:,点不重复的路径,在一个基本路径中有l个不同的结点,v0,v1,vl-1,有

19、l-1条边:,e1,e2,el-1,v0e1v1e2el-1vl-1,基本路径,n阶图:,有n个不同的结点,最多有n-1条边出现在基本路径上,n阶图中的基本路径的长度小于n,2、可达的、不可达的,v1, v2:,图G中的两个结点,从v1到v2至少存在一条路径,从v1到v2 是可达的,否则:从v1到v2不可达的,v1可达v2,在无向图中:,在有向图中:,v2可达v1,v2不一定可达v1,二、连通性,1、无向图的连通性 2、有向图的连通性,1、无向图的连通性,G:无向图,如果G中任意两个结点都相互可达，则称G是连通图。否则称G为非连通图。,1、无向图的连通性,支: 最大的连通子图称为支(或分支)。

20、 注：一个非连通无向图至少有两个以上的支。,h,i,j,具有4个支的非连通无向图,无向图的连通性举例,图G是一个连通无向图 其只有一个最大连通子图，就是其本身G。,无向图的连通性举例,图G是一个非连通无向图, 具有两个支的非连通无向图。,最大连通子图G1 最大连通子图G2,2、有向图的连通性,G:有向图,(1) 强连通图:,任意两结点均相互可达,(2)单向连通图:,任意两结点至少有一结点到另一结点可达,(3)弱连通图:,把有向图看成是无向图是连通的,2、有向图的连通性,强 分 图：最大的强连通子图（强分支）。 单向分图：最大的单向连通子图（单向分支）。 弱 分 图：最大的弱连通子图（弱分支）。

21、,有向图的连通性举例,判断图G1, G2, G3是强连通图、单向连通图还是弱连通图？,解答,v2不可达v3,v3也不可达v2,G1不是单向连通图,G1是弱连通图,解答,v1可达v3,v3不可达v1,G2不是强连通图,v2可达v3,v2可达v1,G2是单向连通图,解答,G3是强连通图,定理,G=: 简单有向图,每一个结点都恰处于一个强分支中（强连通子图）。,分支举例,求图G1和图G2的强分支、单向分支、弱分支。,解答,解答,定理,无向图G（连通或不连通）恰有两个奇结点,必有连接此两结点的路径,证明,设G中的两个奇结点是v1和v2 (1)若G是连通图，则v1和v2之间必有路径； (2)若G是非连通

22、图，则G至少有两个以上的支，因为 支是最大的连通子图(子图也是图)，又因为在任何一个图中奇结点的个数必为偶数个。 所以：v1和v2必处于同一个分支中，即： V1和v2之间必有路径。,第4节 图的矩阵表示,一、邻接矩阵 二、可达性矩阵 三、完全关联矩阵,一、邻接矩阵,1、简单无向图的邻接矩阵 2、简单有向图的邻接矩阵 3、矩阵AAT 4、矩阵ATA 5、矩阵Am,1、简单无向图的邻接矩阵,G:简单无向图,n阶方阵 A=(aij)nn,V=v1,v2,vn,邻接矩阵:,aij=,(vi,vj)E,1,0,否则,邻接矩阵举例,写出简单无向图G对应的邻接矩阵A。,A=,a,b,c,d,e,a,b,c,

23、d,e,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,简单无向图邻接矩阵的特点,(1) 主对角线均为0的对称阵； (2) 每一行（列）中“1”的个数是该行所对应的结点的度； (3) 所有元素均为“0”的邻接矩阵对应的是零图; (4) 除主对角线外所有元素均为“1”的邻接矩阵对应的是完全图。,2、简单有向图的邻接矩阵,G:简单有向图,n阶方阵 A=(aij)nn,V=v1,v2,vn,邻接矩阵:,aij=,E,1,0,否则,邻接矩阵举例,写出简单有向图G对应的邻接矩阵A。,A=,v1,v2,v3,v4,v1,v2,v3,v4,0,1,0,1,

24、1,1,1,0,1,0,1,0,0,0,0,0,简单有向图邻接矩阵的特点,(1) 不一定是对称阵； (2) 每一行中“1”的个数是该行所对应的结点的出度； (3) 每一列中“1”的个数是该列所对应的结点的入度； (4) 第i行中“1”的个数与第i列中“1”的个数之和，恰为记点vi的度。,3、矩阵AAT,A:有向图G的邻接矩阵,AT: A的转置矩阵,A=(aij)nn,B= AAT,=(bij)nn,bij =,A=,vi,vj,ai1,aij,a1j,ain,anj,AT=,a1i,aji,aj1,ani,ajn,ai1 aj1,+ ai2 aj2,+ + ain ajn,解释,aik1,aj

25、k1,aikajk1,为bij的求和中的值增加1,aik1,ajk1,E,E,vk,vj,vi,由vi, vj引出的边共同地终止于结点vk,1n,矩阵AAT的特点,（1）矩阵AAT中的第i行第j列的记入值bij，等于从vi 和vj引出的边能共同地终止于不同结点的数目； （2）对角线上的记入值即为结点vi的出度。,矩阵AAT的举例,已知简单有向图G的邻接矩阵A， 求：矩阵AAT，并指出各记入值的含义。,解答,AAT=,v1,v2,v3,v4,v1,v2,v3,v4,1,1,2,0,2,0,0,0,1,2,0,1,1,1,0,3,4、矩阵ATA,A:有向图G的邻接矩阵,AT:A的转置矩阵,A=(a

26、ij)nn,=a1i a1j,+ a2i a2j,+ + ani anj,矩阵ATA的特点,（1）矩阵ATA中的第i行第j列的记入值，等于从图 G中其它结点引出的边共同地终止于vi和vj的 结点的数目； （2）矩阵ATA中对角线上的记入值即为结点vi的 入度。,矩阵ATA的举例,已知简单有向图G的邻接矩阵A， 求：矩阵ATA，并指出各记入值的含义。,解答,ATA=,v1,v2,v3,v4,v1,v2,v3,v4,1,1,0,1,0,0,0,1,0,1,2,0,2,3,2,1,5、矩阵A2,A:有向图G的邻接矩阵,A2=AA=,( aij(2) )nn,aij(2) =ai1 a1j,+ ai2

27、 a2j,+ + ain anj,解释：,有一条从vi经vk终止于vj的长度为2的路径,aik1,akj1,aikakj1,vi,vj,vk,矩阵Am的特点,aij(2):,从vi到vj长度为2的路径数目,aii(2):,起始于vi又终止于vi的长度为2的回路的数目,aij(m):,从vi到vj长度为m的路径数目,aii(m):,起始于vi又终止于vi的长度为m的回路的数目,矩阵Am的举例,求图G的A2和A3,并说明其中个数据的含义。,解答,A2=,v1,v2,v3,v4,v1,v2,v3,v4,0,0,1,1,0,2,0,1,1,0,0,1,0,1,1,1,解答,A3=,v1,v2,v3,v

28、4,1,1,1,1,1,2,1,0,1,1,1,0,1,2,1,2,v1,v2,v3,v4,定理,G=:,简单有向图,V= v1, v2,vn ,A: G的邻接矩阵,矩阵Am中的元素aij(m):,从vi到vj长度为m的路径数目,证明,对m进行归纳证明： (1)当m=1时，Am=A，根据邻接矩阵的定义显然成立； (2)假设m=k时成立； (3)证明m=k+1时也成立,证明（续）,aij(k),从vi到vj长度为k的路径数目,Ak+1=,AkA=,ai1(k)a1j,+ ai2(k)a2j,+ aih(k)ahj,+ + ain(k)anj,aih(k),从vi到vh长度为k的路径数目,ahj,

29、从vh到vj长度为1的路径数目,aih(k)ahj,从vi经vh到vj长度为k+1的路径数目,对所有h求和:,aij(k+1),从vi到vj长度为k+1的路径总数,m=k+1时成立,举例,求图G的A2、A3和A4 ,并说明其中个数据的含义。,解答,解答,解答,二、可达性矩阵,1、可达性矩阵P 2、求可达性矩阵P的方法,1、可达性矩阵P,G:简单有向图,V=v1,v2,vn,n阶方阵 P=(pij)nn,G的可达性矩阵,pij=,1,0,从vi到vj至少存在一条路径,否则,2、求可达性矩阵P的方法,(1)回忆两个定理 (2)求可达性矩阵P的方法,(1) 回忆两个定理,1) 若存在从vi到vj的路径，则存在从vi到vj的基本路径； 2) n阶图的基本路径长度小于n;,(2) 求可达性矩阵P的方法,A：aij表示从vi到vj长度为1的路径的数目； A2: aij(2)表示从vi到vj长度为2的路径的数目； An: aij(n)表示从vi到vj长度为n的路径的数目； 令：Bn=A+A2+An 其中： Bn中第i行第j列的记入值bij表