第7章+圖論-2(路與連通)

1、1返回 結(jié)束第七章 圖論-1引言引言7.1 圖的基本概念圖的基本概念7.2 路與連通7.3 圖的矩陣表示圖的矩陣表示2返回 結(jié)束7.2 路與連通 內(nèi)容：內(nèi)容：圖的通路，回路，連通性。 重點(diǎn)：重點(diǎn)：1、通路，回路，簡單通路，回路,初級(jí)通路，回路的定義2、圖的連通性的概念3、短程線，距離的概念。3返回 結(jié)束7.2.1 路1、路路 (回路回路)中頂點(diǎn)和邊的交替序列G0 1 1 2llv e v ee v ，其中1(,)iiievv(無向圖)，或1,iiievv(有向圖)，始點(diǎn)始點(diǎn)，0v終點(diǎn)終點(diǎn)，稱為到lv0vlv的路路。當(dāng)0lvv時(shí)， 為回路回路。1v2v3v4v5v1e2e3e4e5e6eG1 1

2、253443562v e v e v e v e v e v125344352v e v e v e v e v4返回 結(jié)束7.2.1 路2.簡單通路、簡單回路 邊不同簡單通路簡單通路 ( (跡跡) )：路中所有的邊都不同：路中所有的邊都不同簡單回路簡單回路 ( (閉跡閉跡) )：回路中所有的邊都不同：回路中所有的邊都不同復(fù)雜通路復(fù)雜通路 ( (回路回路) )：路（回路）中有重復(fù)的邊出現(xiàn)：路（回路）中有重復(fù)的邊出現(xiàn)5返回 結(jié)束7.2.1 路3.初級(jí)通路、初級(jí)回路 初級(jí)（基本）通路，初級(jí)回路：點(diǎn)不同初級(jí)通路初級(jí)通路 ( (路徑路徑) )：路中所有的頂點(diǎn)互不相同：路中所有的頂點(diǎn)互不相同初級(jí)回路初級(jí)

3、回路 ( (圈圈) )：回路中所有的頂點(diǎn)互不相同：回路中所有的頂點(diǎn)互不相同初級(jí)通路 (回路)簡單通路 (回路)，但反之不真。4、路，回路的長度中邊的數(shù)目。6返回 結(jié)束7.2.1 路例例1、(1)例例1 1、(1)圖(1)中，從的路有：到1v6v11 1 2 5 5 76v e v e v e v 21 1 22 3 3 442 5 5 76v e v e v e v e v e v e v 31 1 2 5 5 6442 5 5 76v e v e v e v e v e v e v 長度3長度6長度67返回 結(jié)束7.2.1 路例例1、(1)圖(1)中，從的通路有：到1v6v11 1 2 5

4、5 76v e v e v e v 21 1 22 3 3 442 5 5 76v e v e v e v e v e v e v 31 1 2 5 5 6442 5 5 76v e v e v e v e v e v e v 初級(jí)通路簡單通路復(fù)雜通路8返回 結(jié)束7.2.1 路例例1、(2)1244 3 3 22v e v e v e v 22 5 5 64 3 3 22v e v e v e v e v 3243243256325432vvvvvvveeeveeee 長度3長度4長度7圖(2)中過)有：的回路 (從2v2v到2v9返回 結(jié)束7.2.1 路例例1、(2)1244 3 3 22v

5、 e v e v e v 22 5 5 64 3 3 22v e v e v e v e v 3244 3 3 22 5 5 64 3 3 22v e v e v e v e v e v e v e v 初級(jí)回路(圈)初級(jí)回路(圈)復(fù)雜回路圖(2)中過)有：的回路 (從2v2v到2v10返回 結(jié)束7.2.1 路5、圖中最短的回路如圖： 無向圖中，環(huán)構(gòu)成的回路長為1 ，兩平行邊構(gòu)成的回路長為2。 有向圖中，環(huán)構(gòu)成的回路長為1，兩條方向相反的邊構(gòu)成的回路長為2。11返回 結(jié)束7.2.1 路6、性質(zhì)定理：定理：階圖中，若從頂點(diǎn)nivjv到存在路()ijvv，則從ivjv到存在長度小于等于在一個(gè)的路。

6、1n推論：推論：階圖中，若從頂點(diǎn)nivjv到存在通路()ijvv，則從ivjv到存在長度小于等于在一個(gè)的初級(jí)通路。1n證明思路：多于證明思路：多于n-1條邊的路中必有重復(fù)出現(xiàn)的結(jié)點(diǎn)，反條邊的路中必有重復(fù)出現(xiàn)的結(jié)點(diǎn)，反復(fù)刪去夾在兩個(gè)重復(fù)結(jié)點(diǎn)之間的邊之后，剩余的邊數(shù)不會(huì)復(fù)刪去夾在兩個(gè)重復(fù)結(jié)點(diǎn)之間的邊之后，剩余的邊數(shù)不會(huì)超過超過n-1條邊條邊。 12返回 結(jié)束7.2.1 路6、性質(zhì)定理：定理：階圖中，若niv到自身存在回路，則從到自身存在長度小于等于ivn的回路。在一個(gè)推論：推論：階圖中，若niv到自身存在一個(gè)簡單回路，則從 到自身存在長度小于等于ivn的初級(jí)回路。在一個(gè)由以上定理可知，在階圖中，n

7、任何一條初級(jí)通路的長度任何一條初級(jí)回路的長度1nn13返回 結(jié)束7.2.2 圖的連通性7.2.2 圖的連通性1、連通，可達(dá)。無向圖中，從 到存在路，稱ivjv到ivjv是 連通的連通的( (雙向雙向) )。有向圖中，從 到存在路，稱ivjv可達(dá)可達(dá)ivjv(注意方向)。2、短程線，距離。短程線連通或可達(dá)的兩點(diǎn)間長度最短的 路。距離短程線的長度，記,ijd v v( ,)ijd v v無向圖有向圖14返回 結(jié)束7.2.2 圖的連通性2、短程線，距離若之間無路(或不可達(dá))，規(guī)定,ijv v( ,),ijijd v vd v v 距離滿足：,ijd v v(1)，時(shí)，等號(hào)成立。 ,0ijd v vi

8、jvv(2),ijjkikd v vd v vd v v若是無向圖，還具有對(duì)稱性，( ,)(,)ijjid v vd v v。15返回 結(jié)束7.2.2 圖的連通性3、無向圖的連通。為連通圖為連通圖是平凡圖，或都是連通的。GGG中任兩點(diǎn)為非連通圖為非連通圖G中至少有兩點(diǎn)不連通。G例 1G3G2G1v2v3v4v4u1u2u3u 這里 是連通圖， 是非連通圖，僅有一個(gè)頂點(diǎn)的圖 我們也把它看成是連通圖。 1G2G3G16返回 結(jié)束7.2.2 圖的連通性3、無向圖的連通2G1v2v3v4v4u1u2u3u1v2v3v4v4u1u2u3u 連通圖可以看成是只有一個(gè)連通分支的圖，即 。( )1w G 結(jié)點(diǎn)

9、之間的連通性是結(jié)點(diǎn)集結(jié)點(diǎn)之間的連通性是結(jié)點(diǎn)集V上的等價(jià)關(guān)系，對(duì)應(yīng)該等價(jià)關(guān)系，上的等價(jià)關(guān)系，對(duì)應(yīng)該等價(jià)關(guān)系，必可將作出一個(gè)劃分，把必可將作出一個(gè)劃分，把V分成非空子集分成非空子集V1, V2, , Vm,使得兩個(gè)結(jié)使得兩個(gè)結(jié)點(diǎn)點(diǎn)vj和和vk是連通的，當(dāng)且僅當(dāng)它們屬于同一個(gè)是連通的，當(dāng)且僅當(dāng)它們屬于同一個(gè)Vi 。把子圖把子圖G(V1) , G(V2) , , G(Vm)稱為圖稱為圖G的的連通分支連通分支（connected components）,圖圖G的連通分支數(shù)記為的連通分支數(shù)記為W(G) 。如上例中圖。如上例中圖 的連通分支個(gè)數(shù)就是的連通分支個(gè)數(shù)就是217返回 結(jié)束7.2.2 圖的連通性4、

10、有向圖的連通G中任一對(duì)頂點(diǎn)都互相可達(dá) (雙向)中任一對(duì)頂點(diǎn)至少一向可達(dá)略去 中有向邊的方向后 得到的無向圖連通連通強(qiáng)連通單向連通弱連通強(qiáng)連通單向連通弱連通強(qiáng)連通單向連通GG18返回 結(jié)束7.2.2 圖的連通性例例2單向連通弱連通非連通圖19返回 結(jié)束7.2.2 圖的連通性5 圖與頂點(diǎn)之間的若干關(guān)系圖與頂點(diǎn)之間的若干關(guān)系 把度數(shù)為把度數(shù)為1的頂點(diǎn)稱為的頂點(diǎn)稱為（ pendant nodes）各頂點(diǎn)的度均相同的圖稱為各頂點(diǎn)的度均相同的圖稱為regular graph),各頂點(diǎn)度均為各頂點(diǎn)度均為k的正則圖稱為的正則圖稱為。結(jié)點(diǎn)結(jié)點(diǎn)v，即是把即是把v以及以及與與v關(guān)聯(lián)的邊都刪除。關(guān)聯(lián)的邊都刪除。：，即

11、是把該邊刪，即是把該邊刪除。除。 見見P-282頁的圖頁的圖7-2.2和圖和圖7-2.3。20返回 結(jié)束7.2.3 圖的連通度定義定義7-2.4 圖圖G =是連通圖是連通圖,若有結(jié)點(diǎn)集若有結(jié)點(diǎn)集V1 V,使圖使圖 G中中V1V1連通連通圖圖,則稱則稱V1是是G的一個(gè)的一個(gè)點(diǎn)割集點(diǎn)割集(cut-set of nodes) 。k(G)=min|V1| 是是G的點(diǎn)割集的點(diǎn)割集 稱為圖稱為圖G的的點(diǎn)連通度點(diǎn)連通度(node-connectivity) 。v5v1v2v4v5v1v4點(diǎn)割集點(diǎn)割集V1=v221返回 結(jié)束7.2.3 圖的連通度定義定義7-2.5 圖圖G =是連通圖是連通圖,若有邊集若有邊集

12、E1 E，使圖使圖 G中中E1E1連連通圖，則稱通圖，則稱E1是是G的一個(gè)邊割集的一個(gè)邊割集(cut-set of edges) 。若若某一條邊就構(gòu)成一個(gè)邊割集，則稱該邊為割邊或橋。某一條邊就構(gòu)成一個(gè)邊割集，則稱該邊為割邊或橋。 割邊割邊e使圖使圖G滿足滿足W(G-e)W(G) 。連通度連通度(edge-connectivity) (G)定義定義：非平凡圖的：非平凡圖的邊連通度為邊連通度為 (G)=min |E1| | E1是是G的邊割集的邊割集 邊連通度邊連通度 (G)是為了產(chǎn)生一個(gè)不連通圖需要?jiǎng)h去的邊是為了產(chǎn)生一個(gè)不連通圖需要?jiǎng)h去的邊的最少數(shù)目。對(duì)平凡圖的最少數(shù)目。對(duì)平凡圖G可以定義可以定

13、義 (G)=0，一個(gè)不連通一個(gè)不連通圖也有圖也有 (G)=022返回 結(jié)束7.2.4 二分圖v例：人員分配問題，某公司分配 個(gè)工人做 件工作。代表人的一組頂點(diǎn)用 表示，代表工作的一組頂點(diǎn) 用表示 。 與 相鄰當(dāng)且僅當(dāng)工人 能做工作 ，從而 之間(Y 之間)無邊。所得圖稱為二分圖 。nmnxxxX,2112,mYy yyXjyixixjy 一、一、 二分圖定義二分圖定義 定義定義1： 的二分劃 ，即使 的每條邊的兩個(gè)端點(diǎn)一個(gè)在 中，另一個(gè)在 中。則稱 是二分圖或偶圖， 稱為 的二分劃，記為 。VYXYXGVYX,),(GYX ,G);,(EYXG XYYX ,G23返回 結(jié)束7.2.4 二分圖我

14、們可以驗(yàn)證下面三條成立YX和)(GVXYXGYGG (1) 是的一個(gè)劃分； (2) 和； (3)和均為空?qǐng)D。由以上三條可知，為二分圖。24返回 結(jié)束7.2.4 二分圖123 ,Xv v v123, ,Yu u u1v2v3v1u2u3u圖 是二分圖當(dāng)且僅當(dāng)存在頂點(diǎn)集合的二分劃 ，使 為空?qǐng)D； 當(dāng)且僅當(dāng) 不含長為奇數(shù)的回路； 當(dāng)且僅當(dāng) 的所有非平凡子圖是二分圖。 GYX ,YGXGGG例： 1v2v3v1u2u3u 的一個(gè)回路為若 ，則 類似有所以而 ，故 是偶數(shù)。G34,uX uY1uX212,lluX uYkuY122u uEuY121kCu uu uk利用第二個(gè)等價(jià)刻畫即可。25返回 結(jié)束7.2.4 二分圖定理定理7.2.1 非平凡圖 是二分圖當(dāng)且僅當(dāng) 中不含長為奇數(shù)的回路。GG證明證明必要性是明顯的。充分性充分性：不妨設(shè)G中每一對(duì)頂點(diǎn)之間有路連接（否則只需考慮G的每個(gè)每一對(duì)頂點(diǎn)之間有路連接的極大子圖）。任取G的一個(gè)頂點(diǎn)u，由G的假設(shè)，對(duì)G的每個(gè)頂點(diǎn)v，在G中存在u-v路?，F(xiàn)利用u對(duì)G的頂點(diǎn)進(jìn)行分類。設(shè)V1v|vV(G),G中存在一條長度為偶數(shù)的u-v路V2v|vV(G),G中存在一條長度為奇數(shù)的u-v路顯然uV