第二章 道路與回路1

1、第二章第二章 道路與回路道路與回路2015年秋年秋主要內(nèi)容主要內(nèi)容8:142道路與回路道路與回路8:143P=(e1,e2,e4,e6,e5)每邊首尾相接P= (e1,e2,e3,e8,e5,e4) 有向回路P=(e8,e5,e4) 簡單有向回路 初級1423e1e2e3e4e5e6e749854.5635e88:144 無向圖無向圖定義定義2.1.2： G=(V,E)中，若中，若點(diǎn)邊點(diǎn)邊交替序列交替序列P=(Vi1,ei1,Vi2,ei2,.eiq-1,Viq) 中中Vik與與Vik+1是是eik的兩的兩個(gè)端點(diǎn)，則稱個(gè)端點(diǎn)，則稱P是是G中的一條中的一條鏈或道路鏈或道路。 若若Vi1=Viq則

2、稱則稱P是是G中一個(gè)中一個(gè)圈或回路。圈或回路。 若若P中沒有中沒有重復(fù)出現(xiàn)重復(fù)出現(xiàn)的的邊邊，則為，則為簡單道路簡單道路或或簡單回簡單回路路。 若若P中中沒有重復(fù)沒有重復(fù)的的結(jié)點(diǎn)結(jié)點(diǎn)，則稱為，則稱為初級道路初級道路或或初級回初級回路路。8:1451234道路道路簡單道路：邊不重復(fù)簡單道路：邊不重復(fù)初級道路：點(diǎn)不重復(fù)初級道路：點(diǎn)不重復(fù)回路、簡單回路、初級回路回路、簡單回路、初級回路8:146設(shè)設(shè)C是簡單圖是簡單圖G中含結(jié)點(diǎn)數(shù)大于中含結(jié)點(diǎn)數(shù)大于3的一個(gè)初級回的一個(gè)初級回路路,若結(jié)點(diǎn)若結(jié)點(diǎn)Vi和和Vj在回路在回路C中不相鄰，而邊中不相鄰，而邊(Vi,Vj)是是G的一條邊，則稱的一條邊，則稱C為一條為一

3、條弦弦?；芈分胁幌噜忺c(diǎn)回路中不相鄰點(diǎn)有邊則為弦有邊則為弦弦弦8:14712345定理：定理：若每個(gè)結(jié)點(diǎn)度數(shù)若每個(gè)結(jié)點(diǎn)度數(shù) 3，則，則G中必含中必含帶帶弦弦的的回路回路。8:148證明證明:在在G中構(gòu)造一條最長初級道路中構(gòu)造一條最長初級道路(結(jié)點(diǎn)不重復(fù)結(jié)點(diǎn)不重復(fù))P=(e1,e2,em)，記，記P的起點(diǎn)的起點(diǎn)v0, e1=(v0,v1). 由于由于P是最長的初級道路，所以與是最長的初級道路，所以與V0有邊相連的結(jié)點(diǎn)有邊相連的結(jié)點(diǎn)都在路都在路P上。上。若不在若不在P上，則以該鄰接點(diǎn)為起點(diǎn)，構(gòu)造一上，則以該鄰接點(diǎn)為起點(diǎn)，構(gòu)造一條較條較P多一個(gè)點(diǎn)與邊的新路，與多一個(gè)點(diǎn)與邊的新路，與P是最長的矛盾。是最

4、長的矛盾。 因因deg(Vo) 3，故故V0至少有至少有3個(gè)鄰點(diǎn)，它們在個(gè)鄰點(diǎn)，它們在P中的出中的出現(xiàn)順序現(xiàn)順序,如圖示不妨依次記為如圖示不妨依次記為V1,Vj, Vk。在在P中中V0與與V1直接直接相連，與相連，與Vi,Vj不直接相連不直接相連, 作為作為V0的鄰的鄰 點(diǎn)，當(dāng)然點(diǎn)，當(dāng)然V0與這與這3個(gè)個(gè)鄰點(diǎn)鄰點(diǎn)均有邊直接相連均有邊直接相連, 故存在回路故存在回路V0,V1,Vj, Vk, V0 而而V0與與Vj在在回路回路上上不相鄰不相鄰,故邊故邊(V0,Vi)為為弦弦。 V0V1VJVKP 定理：定理：若每個(gè)結(jié)點(diǎn)度數(shù)若每個(gè)結(jié)點(diǎn)度數(shù) 3，則，則G中必含中必含帶帶弦弦的的回路回路。8:149二

5、分圖二分圖 若能將圖若能將圖G=(V,E)的點(diǎn)集分成互不相干的二部的點(diǎn)集分成互不相干的二部分分X,Y，使得，使得G中每條邊中每條邊e的一個(gè)端點(diǎn)出現(xiàn)在的一個(gè)端點(diǎn)出現(xiàn)在X中，另一個(gè)端點(diǎn)出現(xiàn)在中，另一個(gè)端點(diǎn)出現(xiàn)在Y中，則稱為二分圖。中，則稱為二分圖。e112345e2e3e4e5e68:1410 定理定理：如果二分圖中：如果二分圖中有回路有回路，則它們必由，則它們必由偶偶數(shù)數(shù)邊組成。邊組成。 證明：證明：記回路為記回路為C C ，構(gòu)造法。，構(gòu)造法。 先將回路先將回路C的的所有邊去掉所有邊去掉再加再加, ,記記C的的起點(diǎn)起點(diǎn)x0所所在點(diǎn)集為在點(diǎn)集為X, ,另一端點(diǎn)所在集為另一端點(diǎn)所在集為Y。 從從x0

6、出發(fā)添上邊出發(fā)添上邊e1，e1另一個(gè)端點(diǎn)另一個(gè)端點(diǎn)x1肯定在肯定在Y中中( (因?yàn)橐驗(yàn)槎謭D二分圖) )，再從，再從x1出發(fā)添邊出發(fā)添邊e2，e2另一端點(diǎn)另一端點(diǎn)x2肯肯定在定在X中中( (因?yàn)槎忠驗(yàn)槎謭D圖).).每回到每回到X一次一次需要需要占用回路占用回路C的邊的邊2條。條。 按此方案按此方案來回來回添邊，每添邊，每回到回到X一次一次添加添加2條邊，條邊，設(shè)設(shè)最后回到最后回到x0完成回路完成回路C C的構(gòu)造時(shí)，的構(gòu)造時(shí)，來回來回的次數(shù)為的次數(shù)為K，則共添加了則共添加了2k條邊。即該回路由偶數(shù)條邊組成。條邊。即該回路由偶數(shù)條邊組成。XYx0 x1x2e1e28:1411連通圖與非連通圖連

7、通圖與非連通圖 若若無無向圖向圖G中任意兩點(diǎn)之間都中任意兩點(diǎn)之間都有路有路則為則為連通圖，連通圖， 否則，否則，稱之為稱之為非連通圖非連通圖。 若不管若不管有有向圖中每條邊的方向，即將其向圖中每條邊的方向，即將其視成視成無向圖時(shí)無向圖時(shí)，它是連通的，則稱，它是連通的，則稱G是連通的。是連通的。e11234e2e3e4e7e6e5e11234e2e3e4e7e6e58:1412例題：例題： 設(shè)設(shè)G是簡單圖無向圖，證明當(dāng)邊數(shù)是簡單圖無向圖，證明當(dāng)邊數(shù)m(n-1)(n-2)/2時(shí)，圖時(shí)，圖G是連通圖。是連通圖。證明：證明：假設(shè)假設(shè)G是非連通圖是非連通圖，則至少分成，則至少分成2個(gè)連通分支個(gè)連通分支，

8、記為，記為G1=(V1,E1),G2=(V2,E2)，其中，其中1 |V1|=n1 n-1， 1 |V2|=n2 n-1，即即點(diǎn)數(shù)至少為點(diǎn)數(shù)至少為1，最，最多為多為n-1。由于由于G1是簡單圖是簡單圖(無重邊與環(huán)無重邊與環(huán))，因此，因此m1=|E1| n1(n1-1)/2，n1 n-1 比總點(diǎn)數(shù)少比總點(diǎn)數(shù)少1m2=|E2| n2(n2-1)/2 n2 n-1 比總點(diǎn)數(shù)少比總點(diǎn)數(shù)少1邊數(shù)和邊數(shù)和=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)/2，與，與假設(shè)假設(shè)

9、矛盾。矛盾。 8:1413連通支連通支 若圖若圖G的的連通子圖連通子圖H，不是其它連通子圖的真，不是其它連通子圖的真子圖，則子圖，則H為為G的的最大連通支最大連通支。123451234568:1414樹樹 若圖若圖G G是連通圖，不含有回路，任何兩點(diǎn)之間是連通圖，不含有回路，任何兩點(diǎn)之間只有只有一一條條初級道路初級道路，稱為，稱為樹樹。 邊數(shù)最少的連通圖。邊數(shù)最少的連通圖。1234568:1415主要內(nèi)容主要內(nèi)容8:14162.2道路與回路的判定道路與回路的判定問題:如何判斷一個(gè)圖是連通的! 邊數(shù)(n-1)(n-2)/2的圖肯定是連通的 除了數(shù)邊外還有其他方法嗎? 鄰接矩陣判定法 對鄰接矩陣進(jìn)

10、行矩陣運(yùn)算。判斷v0到每個(gè)結(jié)點(diǎn)是否可通。8:1418基于鄰接矩陣的判定方法（基于鄰接矩陣的判定方法（1） 定理定理: :設(shè)設(shè)A(G)是鄰接矩陣是鄰接矩陣, , 記其記其L次方為次方為AL (G) ， 則其則其i行、行、j列處的元素列處的元素a(L)ij= = G中聯(lián)結(jié)中聯(lián)結(jié)Vi與與Vj的長為的長為L的的道道路的數(shù)目。路的數(shù)目。LnnnnnnnnnnnnLLaaaaaaaaaaaaaaaaaaGAaij.)()(212222111211212222111211)(8:1419vivkvj基于鄰接矩陣的判定方基于鄰接矩陣的判定方法（法（2） 解：解：ViVj長度為長度為2的路，表示該路經(jīng)過兩條邊，

11、的路，表示該路經(jīng)過兩條邊，中間必經(jīng)過一個(gè)結(jié)點(diǎn)中間必經(jīng)過一個(gè)結(jié)點(diǎn)Vk，即即ViVkVj，1kn。 如果如果aik=1, akj=1,即即ViVk,VkVj有邊，則有邊，則ViVkVj有有1條路條路，故故ViVj有長為有長為2的的1條路條路積積aikakj=1。ViVkVj沒有路沒有路 積積aikakj=0k依次取依次取1N，即，即Vk依次取每個(gè)結(jié)點(diǎn)，則依次取每個(gè)結(jié)點(diǎn)，則ai1a1j+ai2a2j +ainanj= 積為積為1的項(xiàng)數(shù)的項(xiàng)數(shù)=長度為長度為2的路的條數(shù)。的路的條數(shù)。8:1420而而ai1 a1j+ai2 a2j +ain anj 是是nnnnnnnnnnnnaaaaaaaaaaaaaa

12、aaaa.212222111211212222111211基于鄰接矩陣的判定方法基于鄰接矩陣的判定方法（3）的第的第i行、第行、第j列處的元素列處的元素,即為即為a(2)ij ，如：，如：a21 a11+a22 a22 +a2n an2為為a(2)21， 因此計(jì)算長度為因此計(jì)算長度為2的路的條數(shù)，可轉(zhuǎn)換為鄰接矩陣相的路的條數(shù)，可轉(zhuǎn)換為鄰接矩陣相乘，乘，長長度為度為2=A*A； 長長度為度為3=A*A*A, 長度為長度為L=A*A*A，L個(gè)個(gè)A相乘。相乘。8:1421A=A2=A3=A4=基于鄰接矩陣的判定方法基于鄰接矩陣的判定方法（4）8:1422 基于鄰接矩陣的判定方法基于鄰接矩陣的判定方法

13、（5）小結(jié)小結(jié)：設(shè)有向圖設(shè)有向圖G=，其結(jié)點(diǎn)數(shù)為，其結(jié)點(diǎn)數(shù)為n，鄰接矩陣，鄰接矩陣為為A。 若要判斷結(jié)點(diǎn)若要判斷結(jié)點(diǎn)Vi到到Vj是否存在一條路，是否存在一條路， 則可計(jì)算則可計(jì)算A，A2,，AL An ， 當(dāng)發(fā)現(xiàn)某個(gè)當(dāng)發(fā)現(xiàn)某個(gè)AL(1L n)的元素的元素a(L)ij=1， 表明結(jié)點(diǎn)表明結(jié)點(diǎn)Vi到到Vj存在存在一條路一條路， 即結(jié)點(diǎn)即結(jié)點(diǎn)Vi到到Vj可達(dá)?？蛇_(dá)。 8:1423基于鄰接矩陣的判定方法基于鄰接矩陣的判定方法（6）定義定義 設(shè)設(shè)G=是一個(gè)簡單有向圖，是一個(gè)簡單有向圖，|V|=n，結(jié)點(diǎn)已編序即結(jié)點(diǎn)已編序即V=v0, v1, vn，則，則可達(dá)性可達(dá)性矩陣矩陣（道路矩陣）（道路矩陣）P=(p

14、ij) nxn定義如下：定義如下： 從從Vi到到Vj至少存在至少存在一條路時(shí)一條路時(shí) pij=1, 從從Vi到到Vj不存在不存在路時(shí)路時(shí) pij=0。 可達(dá)性矩陣可達(dá)性矩陣表明表明： 圖中任意兩結(jié)點(diǎn)間圖中任意兩結(jié)點(diǎn)間是否至少有一是否至少有一條路，條路， pij=1？ 及在任一結(jié)點(diǎn)上及在任一結(jié)點(diǎn)上是否有回路是否有回路，pii=1？8:1424無路相通無路相通若若有路相通有路相通若若jijiijvvvvp, ,0, , 1A=B=基于鄰接矩陣的判定方法基于鄰接矩陣的判定方法（7） 由鄰接矩陣由鄰接矩陣A計(jì)算可達(dá)性矩陣計(jì)算可達(dá)性矩陣P的方法：的方法：1、B=A+A2+A3+An2、將、將B中不為零中

15、不為零的元素均改換為的元素均改換為1， 為零的元素不變，即為為零的元素不變，即為可達(dá)性矩陣可達(dá)性矩陣P。8:1425基于鄰接矩陣的判定方法基于鄰接矩陣的判定方法（8）注意：注意： 在在計(jì)算計(jì)算P時(shí)，在每個(gè)時(shí)，在每個(gè)AL中中,對于兩個(gè)結(jié)點(diǎn)間對于兩個(gè)結(jié)點(diǎn)間具有路的具有路的數(shù)目不感興趣數(shù)目不感興趣，只要有一條路只要有一條路即即可，表明兩結(jié)點(diǎn)間是否有路即可。可，表明兩結(jié)點(diǎn)間是否有路即可。 因此因此，可將矩陣可將矩陣A，A2，An分別改為分別改為布爾矩布爾矩陣陣A(1),A(2),A(n), 于是于是，計(jì)算計(jì)算P可簡化為可簡化為:P=A(1) A(2) A(n) 其中其中A(i)表示布爾運(yùn)算意義下的表示

16、布爾運(yùn)算意義下的A的的i次方。次方。8:1426基于鄰接矩陣的判定方法（基于鄰接矩陣的判定方法（9） 例271100001000001010001000101)2(A0100010000000100010100010A1100010000000100010100010)3(A1100001000001010001000101)4(A1100011000001110011100111 )4()3()2(AAAAv3v2v1v4v5基于鄰接矩陣的判定方法基于鄰接矩陣的判定方法（9）8:1428例例WarShall算法算法1. PA2. for i=1 to n do3. for j=1 to n

17、do4. for k=1 to n do pjk pjk (pji pik) 8:1429無路相通無路相通若若有路相通有路相通若若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值加值加18:1430 11111111111111111111111111001110001110111100001000011011110000108:1431

18、1423e1e2e3e4e5 1100000001001110 長度為2的路條數(shù)長度為3的路條數(shù)長度為4的路條數(shù)可達(dá)性矩陣Warshall算法8:1432搜索法搜索法-判斷是否有路判斷是否有路常用方法：常用方法： BFS(Breadth First Search)廣度優(yōu)先廣度優(yōu)先 BFS從從起點(diǎn)起點(diǎn)V0出發(fā)，找它的出發(fā)，找它的直接后繼集直接后繼集A1，再求出再求出A1每個(gè)結(jié)點(diǎn)的后繼集每個(gè)結(jié)點(diǎn)的后繼集(剔除已遍歷剔除已遍歷結(jié)點(diǎn)結(jié)點(diǎn))A2，直到直到Ai中含有終點(diǎn)中含有終點(diǎn)Vj為止。為止。 DFS(Depth First Search)深度優(yōu)深度優(yōu)先先 利用正向表，開始全部標(biāo)記利用正向表，開始全部標(biāo)記0，已屬于，已屬于某個(gè)集合的元素置為某個(gè)集合的元素置為1。8:1433162345判斷1是否連到各點(diǎn)？廣度優(yōu)廣度優(yōu)先先正向表正向表 直接后繼集直接后繼集+(v1)=v2,v6, = A1 =v2,v6 +(v2)=v3,