第二章道路与回路1

1、第二章第二章 道路与回路道路与回路2015年秋年秋主要内容主要内容12:102道路与回路道路与回路12:103P=(e1,e2,e4,e6,e5)每边首尾相接P= (e1,e2,e3,e8,e5,e4) 有向回路P=(e8,e5,e4) 简单有向回路 初级1423e1e2e3e4e5e6e749854.5635e812:104 无向图无向图定义定义2.1.2： G=(V,E)中，若中，若点边点边交替序列交替序列P=(Vi1,ei1,Vi2,ei2,.eiq-1,Viq) 中中Vik与与Vik+1是是eik的两的两个端点，则称个端点，则称P是是G中的一条中的一条链或道路链或道路。 若若Vi1=V

2、iq则称则称P是是G中一个中一个圈或回路。圈或回路。 若若P中没有中没有重复出现重复出现的的边边，则为，则为简单道路简单道路或或简单回简单回路路。 若若P中中没有重复没有重复的的结点结点，则称为，则称为初级道路初级道路或或初级回初级回路路。12:1051234道路道路简单道路：边不重复简单道路：边不重复初级道路：点不重复初级道路：点不重复回路、简单回路、初级回路回路、简单回路、初级回路12:106设设C是简单图是简单图G中含结点数大于中含结点数大于3的一个初级回的一个初级回路路,若结点若结点Vi和和Vj在回路在回路C中不相邻，而边中不相邻，而边(Vi,Vj)是是G的一条边，则称的一条边，则称C

3、为一条为一条弦弦。回路中不相邻点回路中不相邻点有边则为弦有边则为弦弦弦12:10712345定理：定理：若每个结点度数若每个结点度数 3，则，则G中必含中必含带带弦弦的的回路回路。12:108证明证明:在在G中构造一条最长初级道路中构造一条最长初级道路(结点不重复结点不重复)P=(e1,e2,em)，记，记P的起点的起点v0, e1=(v0,v1). 由于由于P是最长的初级道路，所以与是最长的初级道路，所以与V0有边相连的结点有边相连的结点都在路都在路P上。上。若不在若不在P上，则以该邻接点为起点，构造一上，则以该邻接点为起点，构造一条较条较P多一个点与边的新路，与多一个点与边的新路，与P是最

4、长的矛盾。是最长的矛盾。 因因deg(Vo) 3，故故V0至少有至少有3个邻点，它们在个邻点，它们在P中的出中的出现顺序现顺序,如图示不妨依次记为如图示不妨依次记为V1,Vj, Vk。在在P中中V0与与V1直接直接相连，与相连，与Vi,Vj不直接相连不直接相连, 作为作为V0的邻的邻 点，当然点，当然V0与这与这3个个邻点邻点均有边直接相连均有边直接相连, 故存在回路故存在回路V0,V1,Vj, Vk, V0 而而V0与与Vj在在回路回路上上不相邻不相邻,故边故边(V0,Vi)为为弦弦。 V0V1VJVKP 定理：定理：若每个结点度数若每个结点度数 3，则，则G中必含中必含带带弦弦的的回路回路

5、。12:109二分图二分图 若能将图若能将图G=(V,E)的点集分成互不相干的二部的点集分成互不相干的二部分分X,Y，使得，使得G中每条边中每条边e的一个端点出现在的一个端点出现在X中，另一个端点出现在中，另一个端点出现在Y中，则称为二分图。中，则称为二分图。e112345e2e3e4e5e612:1010 定理定理：如果二分图中：如果二分图中有回路有回路，则它们必由，则它们必由偶偶数数边组成。边组成。 证明：证明：记回路为记回路为C C ，构造法。，构造法。 先将回路先将回路C的的所有边去掉所有边去掉再加再加, ,记记C的的起点起点x0所所在点集为在点集为X, ,另一端点所在集为另一端点所在

6、集为Y。 从从x0出发添上边出发添上边e1，e1另一个端点另一个端点x1肯定在肯定在Y中中( (因为因为二分图二分图) )，再从，再从x1出发添边出发添边e2，e2另一端点另一端点x2肯肯定在定在X中中( (因为二分因为二分图图).).每回到每回到X一次一次需要需要占用回路占用回路C的边的边2条。条。 按此方案按此方案来回来回添边，每添边，每回到回到X一次一次添加添加2条边，条边，设设最后回到最后回到x0完成回路完成回路C C的构造时，的构造时，来回来回的次数为的次数为K，则共添加了则共添加了2k条边。即该回路由偶数条边组成。条边。即该回路由偶数条边组成。XYx0 x1x2e1e212:101

7、1连通图与非连通图连通图与非连通图 若若无无向图向图G中任意两点之间都中任意两点之间都有路有路则为则为连通图，连通图， 否则，否则，称之为称之为非连通图非连通图。 若不管若不管有有向图中每条边的方向，即将其向图中每条边的方向，即将其视成视成无向图时无向图时，它是连通的，则称，它是连通的，则称G是连通的。是连通的。e11234e2e3e4e7e6e5e11234e2e3e4e7e6e512:1012例题：例题： 设设G是简单图无向图，证明当边数是简单图无向图，证明当边数m(n-1)(n-2)/2时，图时，图G是连通图。是连通图。证明：证明：假设假设G是非连通图是非连通图，则至少分成，则至少分成2

8、个连通分支个连通分支，记为，记为G1=(V1,E1),G2=(V2,E2)，其中，其中1 |V1|=n1 n-1， 1 |V2|=n2 n-1，即即点数至少为点数至少为1，最，最多为多为n-1。由于由于G1是简单图是简单图(无重边与环无重边与环)，因此，因此m1=|E1| n1(n1-1)/2，n1 n-1 比总点数少比总点数少1m2=|E2| n2(n2-1)/2 n2 n-1 比总点数少比总点数少1边数和边数和=m=|E1|+|E2| n1(n1-1)/2+ n2(n2-1)/2 (n-1)(n1-1)/2+(n-1)(n2-1)/2 =(n-1)(n1+n2-2)/2=(n-1)(n-2

9、)/2，与，与假设假设矛盾。矛盾。 12:1013连通支连通支 若图若图G的的连通子图连通子图H，不是其它连通子图的真，不是其它连通子图的真子图，则子图，则H为为G的的最大连通支最大连通支。1234512345612:1014树树 若图若图G G是连通图，不含有回路，任何两点之间是连通图，不含有回路，任何两点之间只有只有一一条条初级道路初级道路，称为，称为树树。 边数最少的连通图。边数最少的连通图。12345612:1015主要内容主要内容12:10162.2道路与回路的判定道路与回路的判定问题:如何判断一个图是连通的! 边数(n-1)(n-2)/2的图肯定是连通的 除了数边外还有其他方法吗?

10、 邻接矩阵判定法 对邻接矩阵进行矩阵运算。判断v0到每个结点是否可通。12:1018基于邻接矩阵的判定方法（基于邻接矩阵的判定方法（1） 定理定理: :设设A(G)是邻接矩阵是邻接矩阵, , 记其记其L次方为次方为AL (G) ， 则其则其i行、行、j列处的元素列处的元素a(L)ij= = G中联结中联结Vi与与Vj的长为的长为L的的道道路的数目。路的数目。LnnnnnnnnnnnnLLaaaaaaaaaaaaaaaaaaGAaij.)()(212222111211212222111211)(12:1019vivkvj基于邻接矩阵的判定方基于邻接矩阵的判定方法（法（2） 解：解：ViVj长度为

11、长度为2的路，表示该路经过两条边，的路，表示该路经过两条边，中间必经过一个结点中间必经过一个结点Vk，即即ViVkVj，1kn。 如果如果aik=1, akj=1,即即ViVk,VkVj有边，则有边，则ViVkVj有有1条路条路，故故ViVj有长为有长为2的的1条路条路积积aikakj=1。ViVkVj没有路没有路 积积aikakj=0k依次取依次取1N，即，即Vk依次取每个结点，则依次取每个结点，则ai1a1j+ai2a2j +ainanj= 积为积为1的项数的项数=长度为长度为2的路的条数。的路的条数。12:1020而而ai1 a1j+ai2 a2j +ain anj 是是nnnnnnnn

12、nnnnaaaaaaaaaaaaaaaaaa.212222111211212222111211基于邻接矩阵的判定方法基于邻接矩阵的判定方法（3）的第的第i行、第行、第j列处的元素列处的元素,即为即为a(2)ij ，如：，如：a21 a11+a22 a22 +a2n an2为为a(2)21， 因此计算长度为因此计算长度为2的路的条数，可转换为邻接矩阵相的路的条数，可转换为邻接矩阵相乘，乘，长长度为度为2=A*A； 长长度为度为3=A*A*A, 长度为长度为L=A*A*A，L个个A相乘。相乘。12:1021A=A2=A3=A4=基于邻接矩阵的判定方法基于邻接矩阵的判定方法（4）12:1022 基于

13、邻接矩阵的判定方法基于邻接矩阵的判定方法（5）小结小结：设有向图设有向图G=，其结点数为，其结点数为n，邻接矩阵，邻接矩阵为为A。 若要判断结点若要判断结点Vi到到Vj是否存在一条路，是否存在一条路， 则可计算则可计算A，A2,，AL An ， 当发现某个当发现某个AL(1L n)的元素的元素a(L)ij=1， 表明结点表明结点Vi到到Vj存在存在一条路一条路， 即结点即结点Vi到到Vj可达。可达。 12:1023基于邻接矩阵的判定方法基于邻接矩阵的判定方法（6）定义定义 设设G=是一个简单有向图，是一个简单有向图，|V|=n，结点已编序即结点已编序即V=v0, v1, vn，则，则可达性可达

14、性矩阵矩阵（道路矩阵）（道路矩阵）P=(pij) nxn定义如下：定义如下： 从从Vi到到Vj至少存在至少存在一条路时一条路时 pij=1, 从从Vi到到Vj不存在不存在路时路时 pij=0。 可达性矩阵可达性矩阵表明表明： 图中任意两结点间图中任意两结点间是否至少有一是否至少有一条路，条路， pij=1？ 及在任一结点上及在任一结点上是否有回路是否有回路，pii=1？12:1024无路相通无路相通若若有路相通有路相通若若jijiijvvvvp, ,0, , 1A=B=基于邻接矩阵的判定方法基于邻接矩阵的判定方法（7） 由邻接矩阵由邻接矩阵A计算可达性矩阵计算可达性矩阵P的方法：的方法：1、B

15、=A+A2+A3+An2、将、将B中不为零中不为零的元素均改换为的元素均改换为1， 为零的元素不变，即为为零的元素不变，即为可达性矩阵可达性矩阵P。12:1025基于邻接矩阵的判定方法基于邻接矩阵的判定方法（8）注意：注意： 在在计算计算P时，在每个时，在每个AL中中,对于两个结点间对于两个结点间具有路的具有路的数目不感兴趣数目不感兴趣，只要有一条路只要有一条路即即可，表明两结点间是否有路即可。可，表明两结点间是否有路即可。 因此因此，可将矩阵可将矩阵A，A2，An分别改为分别改为布尔矩布尔矩阵阵A(1),A(2),A(n), 于是于是，计算计算P可简化为可简化为:P=A(1) A(2) A(

16、n) 其中其中A(i)表示布尔运算意义下的表示布尔运算意义下的A的的i次方。次方。12:1026基于邻接矩阵的判定方法（基于邻接矩阵的判定方法（9） 例271100001000001010001000101)2(A0100010000000100010100010A1100010000000100010100010)3(A1100001000001010001000101)4(A1100011000001110011100111 )4()3()2(AAAAv3v2v1v4v5基于邻接矩阵的判定方法基于邻接矩阵的判定方法（9）12:1028例例WarShall算法算法1. PA2. for i=

17、1 to n do3. for j=1 to n do4. for k=1 to n do pjk pjk (pji pik) 12:1029无路相通无路相通若若有路相通有路相通若若jijiijvvvvp, ,0, , 1WarShall算法算法WarShall算法算法：for i=1 to n /从第从第1列到第列到第N列列 for j=1 to n /每列从每列从1行到第行到第N行行 if (aj,i=1) 第第j行行=第第j行行第第i行行 /行号行号J值加值加1 / 列号列号I值加值加112:1030 1111111111111111111111111100111000111011110

18、00010000110111100001012:10311423e1e2e3e4e5 1100000001001110 长度为2的路条数长度为3的路条数长度为4的路条数可达性矩阵Warshall算法12:1032搜索法搜索法-判断是否有路判断是否有路常用方法：常用方法： BFS(Breadth First Search)广度优先广度优先 BFS从从起点起点V0出发，找它的出发，找它的直接后继集直接后继集A1，再求出再求出A1每个结点的后继集每个结点的后继集(剔除已遍历剔除已遍历结点结点)A2，直到直到Ai中含有终点中含有终点Vj为止。为止。 DFS(Depth First Search)深度优深度优先先 利用正向表，开始全部标记利用正向表，开始全部标记0，已属于，已属于某个集合的元素置为某个集合的元素置为1。12:1033162345判断1是否连到各点？广度优广度优先先正向表正向表 直接后继集直接后继集+(v1)=v2,v6, = A1 =v2,v6 +(v2)=v3,v6+