離散數(shù)學(xué)--第7章+圖論-2ppt課件

1、1返回 結(jié)束第七章 圖論-1引言引言7.1 圖的基本概念圖的基本概念7.2 路與連通路與連通7.3 圖的矩陣表示圖的矩陣表示7.4 最短路徑問(wèn)題最短路徑問(wèn)題7.5 圖的匹配圖的匹配8.1 Euler圖和圖和Hamilton圖圖8.2 樹(shù)樹(shù)8.3 生成樹(shù)生成樹(shù) 8.4 平面圖平面圖2返回 結(jié)束7.2 路與連通 內(nèi)容：圖的通路，回路，連通性。內(nèi)容：圖的通路，回路，連通性。 重點(diǎn)：重點(diǎn)：1、通路，回路，簡(jiǎn)單通路，回路、通路，回路，簡(jiǎn)單通路，回路,初級(jí)通路，回路的初級(jí)通路，回路的定義定義2、圖的連通性的概念、圖的連通性的概念3、短程線，距離的概念。、短程線，距離的概念。3返回 結(jié)束7.2.1 路1、路

2、 (回路)中頂點(diǎn)和邊的交替序列G0 1 1 2llv e v ee v ，其中1(,)iiievv(無(wú)向圖)，或1,iiievv(有向圖)，始點(diǎn)，0v終點(diǎn)，稱為到lv0vlv的路。當(dāng)0lvv時(shí)， 為回路。1v2v3v4v5v1e2e3e4e5e6eG1 1253443562v e v e v e v e v e v125344352v e v e v e v e v4返回 結(jié)束7.2.1 路2.簡(jiǎn)單通路、簡(jiǎn)單回路 邊不同簡(jiǎn)單通路簡(jiǎn)單通路 ( (跡跡) )：路中所有的邊都不同：路中所有的邊都不同簡(jiǎn)單回路簡(jiǎn)單回路 ( (閉跡閉跡) )：回路中所有的邊都不同：回路中所有的邊都不同復(fù)雜通路復(fù)雜通路 (

3、 (回路回路) )：路回路中有重復(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í)回路 ( (圈圈) )：回路中所有的頂點(diǎn)互不相同：回路中所有的頂點(diǎn)互不相同初級(jí)通路 (回路)簡(jiǎn)單通路 (回路)，但反之不真。4、路，回路的長(zhǎng)度中邊的數(shù)目。6返回 結(jié)束7.2.1 路例例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

4、v e v e v e v e v e v 31 1 2 5 5 64 42 5 5 76v ev e v e v e v e v e v 長(zhǎng)度3長(zhǎng)度6長(zhǎng)度67返回 結(jié)束7.2.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 64 42 5 5 76v ev e v e v e v e v e v 初級(jí)通路簡(jiǎn)單通路復(fù)雜通路8返回 結(jié)束7.2.1 路例例1、(2)1244 3 3 22v e v e v e v 22 5

5、 5 64 3 3 22v e v e v e v e v 3243243256325432vvvvvvveeeveeee 長(zhǎng)度3長(zhǎng)度4長(zhǎng)度7圖(2)中過(guò))有：的回路 (從2v2v到2v9返回 結(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 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)中過(guò))有：的回路 (從2v2v到2v10返回 結(jié)束7.2.1 路5、圖中最短的回路如圖： 無(wú)向圖中，環(huán)

6、構(gòu)成的回路長(zhǎng)為無(wú)向圖中，環(huán)構(gòu)成的回路長(zhǎng)為1 1 ，兩平行邊構(gòu)成的回路長(zhǎng)為，兩平行邊構(gòu)成的回路長(zhǎng)為2 2。 有向圖中，環(huán)構(gòu)成的回路長(zhǎng)為有向圖中，環(huán)構(gòu)成的回路長(zhǎng)為1 1，兩條方向相反的邊構(gòu)成的回路，兩條方向相反的邊構(gòu)成的回路長(zhǎng)為長(zhǎng)為2 2。11返回 結(jié)束7.2.1 路6、性質(zhì)定理：定理：階圖中，若從頂點(diǎn)nivjv到存在路()ijvv，則從ivjv到存在長(zhǎng)度小于等于在一個(gè)的路。1n推論：推論：階圖中，若從頂點(diǎn)nivjv到存在通路()ijvv，則從ivjv到存在長(zhǎng)度小于等于在一個(gè)的初級(jí)通路。1n證明思路：多于證明思路：多于n-1n-1條邊的路中必有重復(fù)出現(xiàn)的結(jié)點(diǎn)，反條邊的路中必有重復(fù)出現(xiàn)的結(jié)點(diǎn)，反復(fù)刪

7、去夾在兩個(gè)重復(fù)結(jié)點(diǎn)之間的邊之后，剩余的邊數(shù)不會(huì)復(fù)刪去夾在兩個(gè)重復(fù)結(jié)點(diǎn)之間的邊之后，剩余的邊數(shù)不會(huì)超過(guò)超過(guò)n-1n-1條邊。條邊。 12返回 結(jié)束7.2.1 路6、性質(zhì)定理：定理：階圖中，假設(shè)niv到自身存在回路，則從到自身存在長(zhǎng)度小于等于ivn的回路。在一個(gè)推論：推論：階圖中，假設(shè)niv到自身存在一個(gè)簡(jiǎn)單回路，則從 到自身存在長(zhǎng)度小于等于ivn的初級(jí)回路。在一個(gè)由以上定理可知，在階圖中，n任何一條初級(jí)通路的長(zhǎng)度任何一條初級(jí)回路的長(zhǎng)度1nn13返回 結(jié)束7.2.2 圖的連通性7.2.2 圖的連通性1、連通，可達(dá)。無(wú)向圖中，從 到存在路，稱ivjv到ivjv是 連通的連通的( (雙向雙向) )。有

8、向圖中，從 到存在路，稱ivjv可達(dá)可達(dá)ivjv(注意方向)。2、短程線，間隔。短程線連通或可達(dá)的兩點(diǎn)間長(zhǎng)度最短的 路。間隔短程線的長(zhǎng)度，記,ijd v v( ,)ijd v v無(wú)向圖有向圖14返回 結(jié)束7.2.2 圖的連通性2、短程線，間隔假設(shè)之間無(wú)路(或不可達(dá))，規(guī)定,ijv v( ,),ijijd v vd v v 間隔滿足：,ijd v v(1)，時(shí)，等號(hào)成立。 ,0ijd v vijvv(2),ijjkikd v vd v vd v v若是無(wú)向圖，還具有對(duì)稱性，( ,)(,)ijjid v vd v v。15返回 結(jié)束7.2.2 圖的連通性3、無(wú)向圖的連通。為連通圖為連通圖是平凡圖，

9、或都是連通的。GGG中任兩點(diǎn)為非連通圖為非連通圖G中至少有兩點(diǎn)不連通。G例 1G3G2G1v2v3v4v4u1u2u3u 這里 是連通圖， 是非連通圖，僅有一個(gè)頂點(diǎn)的圖 我們也把它看成是連通圖。 1G2G3G16返回 結(jié)束7.2.2 圖的連通性3、無(wú)向圖的連通2G1v2v3v4v4u1u2u3u1v2v3v4v4u1u2u3u 連通圖可以看成是只有一個(gè)連通分支的圖，即 。( )1w G 17返回 結(jié)束7.2.2 圖的連通性4、有向圖的連通G中任一對(duì)頂點(diǎn)都互相可達(dá) (雙向)中任一對(duì)頂點(diǎn)至少一向可達(dá)略去 中有向邊的方向后 得到的無(wú)向圖連通連通強(qiáng)連通單向連通弱連通強(qiáng)連通單向連通弱連通強(qiáng)連通單向連通G

10、G18返回 結(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)（的頂點(diǎn)稱為懸掛點(diǎn)（ pendant nodes）各頂點(diǎn)的度均相同的圖稱為正則圖各頂點(diǎn)的度均相同的圖稱為正則圖(regular graph),各頂點(diǎn)度均為各頂點(diǎn)度均為k的正則圖稱為的正則圖稱為k-正則正則圖。圖。刪除結(jié)點(diǎn)：所謂在圖中刪除結(jié)點(diǎn)刪除結(jié)點(diǎn)：所謂在圖中刪除結(jié)點(diǎn)v，即是把，即是把v以以及與及與v關(guān)聯(lián)的邊都刪除。關(guān)聯(lián)的邊都刪除。刪除邊：所謂在圖中刪除某條邊，即是把該邊刪除邊：所謂在圖中刪除某條邊，即是把該邊

11、刪除。刪除。 見(jiàn)見(jiàn)P-282頁(yè)的圖頁(yè)的圖7-2.2和圖和圖7-2.3。20返回 結(jié)束7.2.3 圖的連通度定義定義7-2.4 設(shè)無(wú)向圖設(shè)無(wú)向圖G =是連通圖是連通圖,若有結(jié)點(diǎn)集若有結(jié)點(diǎn)集V1V,使圖使圖 G中刪除了中刪除了V1的所有結(jié)點(diǎn)后的所有結(jié)點(diǎn)后,所得到的子圖是不連通所得到的子圖是不連通圖圖,而刪除了而刪除了V1的任何真子集后的任何真子集后,所得到的子圖仍是連通所得到的子圖仍是連通圖圖,則稱則稱V1是是G的一個(gè)點(diǎn)割集的一個(gè)點(diǎn)割集(cut-set of nodes) 。k(G)=min|V1| 是是G的點(diǎn)割集的點(diǎn)割集 稱為圖稱為圖G的點(diǎn)連通度的點(diǎn)連通度(node-connectivity)

12、。v5v1v2v4v5v1v4點(diǎn)割集點(diǎn)割集V1=v2V1=v221返回 結(jié)束7.2.3 圖的連通度定義定義7-2.5 設(shè)無(wú)向圖設(shè)無(wú)向圖G =是連通圖是連通圖,若有邊集若有邊集E1E，使圖使圖 G中刪除了中刪除了E1的所有邊后，所得到的子圖是不連通的所有邊后，所得到的子圖是不連通圖，而刪除了圖，而刪除了E1的任何真子集后，所得到的子圖仍是連的任何真子集后，所得到的子圖仍是連通圖，則稱通圖，則稱E1是是G的一個(gè)邊割集的一個(gè)邊割集(cut-set of edges) 。若。若某一條邊就構(gòu)成一個(gè)邊割集，則稱該邊為割邊或橋。某一條邊就構(gòu)成一個(gè)邊割集，則稱該邊為割邊或橋。 割邊割邊e使圖使圖G滿足滿足W(

13、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可以定義可以定義 (G)=0，一個(gè)不連，一個(gè)不連通圖也有通圖也有 (G)=022返回 結(jié)束7.2.4 二分圖v例：人員分配問(wèn)題，某公司分配 個(gè)工人做 件工作。代表人的一組頂點(diǎn)用 表示，代表工作的一組頂點(diǎn) 用表示 。 與 相鄰當(dāng)且僅當(dāng)工人 能做工作 ，從而 之間(Y 之間)

14、無(wú)邊。所得圖稱為二分圖 。nmnxxxX,2112,mYy yyXjyixixjy 一、一、 二分圖定義二分圖定義 定義定義1： 的二分劃的二分劃 ，即，即使使 的每條邊的兩個(gè)端點(diǎn)一個(gè)在的每條邊的兩個(gè)端點(diǎn)一個(gè)在 中，另一個(gè)在中，另一個(gè)在 中。則稱中。則稱 是二是二分圖或偶圖，分圖或偶圖， 稱為稱為 的二分劃，記為的二分劃，記為 。VYXYXGVYX,),(GYX ,G);,(EYXG XYYX ,G23返回 結(jié)束7.2.4 二分圖我們可以驗(yàn)證下面三條成立YX和)(GVXYXGYGG (1) 是的一個(gè)劃分； (2) 和； (3)和均為空?qǐng)D。由以上三條可知，為二分圖。24返回 結(jié)束7.2.4 二分

15、圖123 ,Xv v v123, ,Yu u u1v2v3v1u2u3u圖 是二分圖當(dāng)且僅當(dāng)存在頂點(diǎn)集合的二分劃 ，使 為空?qǐng)D； 當(dāng)且僅當(dāng) 不含長(zhǎng)為奇數(shù)的回路； 當(dāng)且僅當(dāng) 的所有非平凡子圖是二分圖。 GYX ,YGXGGG例： 1v2v3v1u2u3u 的一個(gè)回路為假設(shè) ，那么 類似有所以而 ，故 是偶數(shù)。G34,uX uY1uX212,lluX uYkuY122u uEuY121kCu uu uk利用第二個(gè)等價(jià)刻畫即可。25返回 結(jié)束7.2.4 二分圖定理定理7.2.1 非平凡圖非平凡圖 是二分圖當(dāng)且僅當(dāng)是二分圖當(dāng)且僅當(dāng) 中中不含長(zhǎng)為奇數(shù)的回路。不含長(zhǎng)為奇數(shù)的回路。GG證明必要性是明顯的。證

16、明必要性是明顯的。充分性：不妨設(shè)充分性：不妨設(shè)G中每一對(duì)頂點(diǎn)之間有路連接否則中每一對(duì)頂點(diǎn)之間有路連接否則只需考慮只需考慮G的每個(gè)每一對(duì)頂點(diǎn)之間有路連接的極大子的每個(gè)每一對(duì)頂點(diǎn)之間有路連接的極大子圖）。任取圖）。任取G的一個(gè)頂點(diǎn)的一個(gè)頂點(diǎn)u，由，由G的假設(shè)，對(duì)的假設(shè)，對(duì)G的每個(gè)頂?shù)拿總€(gè)頂點(diǎn)點(diǎn)v，在，在G中存在中存在u-v路?，F(xiàn)利用路。現(xiàn)利用u對(duì)對(duì)G的頂點(diǎn)進(jìn)行分類。的頂點(diǎn)進(jìn)行分類。設(shè)設(shè)V1v|vV(G),G中存在一條長(zhǎng)度為偶數(shù)的中存在一條長(zhǎng)度為偶數(shù)的u-v路路V2v|vV(G),G中存在一條長(zhǎng)度為奇數(shù)的中存在一條長(zhǎng)度為奇數(shù)的u-v路路顯然顯然uV1。由于圖。由于圖G中不存在長(zhǎng)度為奇數(shù)的圈，所以對(duì)中不存在長(zhǎng)