離散數(shù)學(xué)基礎(chǔ) 第六章 圖論

1、1第六章 圖離散數(shù)學(xué)基礎(chǔ)離散數(shù)學(xué)基礎(chǔ)謝勝利謝勝利2 煤氣管道的鋪設(shè)問題?，F(xiàn)為城市的各小區(qū)之間鋪設(shè)煤氣煤氣管道的鋪設(shè)問題。現(xiàn)為城市的各小區(qū)之間鋪設(shè)煤氣管道管道(如下圖所示如下圖所示)，對，對 n 個小區(qū)只需鋪設(shè)個小區(qū)只需鋪設(shè) n-1 條管線，由于地條管線，由于地理環(huán)境不同等因素使各條管線所需投資不同，如何使投資成理環(huán)境不同等因素使各條管線所需投資不同，如何使投資成本最低？本最低？ ABDFE51372364108圖論問題3第1節(jié) 圖的基本概念45 67 81無向圖和有向圖無向圖和有向圖9l無向邊無向邊，例：，例： e3 = （v3,v4） = （v4,v3） l有向邊有向邊(弧弧)，例：，例：

2、e8 = e3v3v4e8v2v310有向圖有向圖無向圖無向圖2、圖的基本術(shù)語、圖的基本術(shù)語有向圖：有向圖：圖中各邊都是有向邊圖中各邊都是有向邊無向圖：無向圖：圖中各邊都是無向邊圖中各邊都是無向邊混合圖：混合圖：圖中既有有向邊又有無向邊圖中既有有向邊又有無向邊11 無向圖邊與邊的鄰接無向圖邊與邊的鄰接：有公共端點(diǎn)的邊互為鄰接邊：有公共端點(diǎn)的邊互為鄰接邊1e2e3e4e5e12有限圖：有限圖：圖中僅有有限個頂點(diǎn)。圖中僅有有限個頂點(diǎn)。（無限圖：圖中有無限個頂點(diǎn)。）（無限圖：圖中有無限個頂點(diǎn)。）N階圖：階圖：具有具有n個頂點(diǎn)的有限圖。個頂點(diǎn)的有限圖。零圖：零圖：只有頂點(diǎn)而沒有邊的圖只有頂點(diǎn)而沒有邊的

3、圖平行邊：平行邊：兩頂點(diǎn)之間有多條邊（若為有向圖則方向也相同）。兩頂點(diǎn)之間有多條邊（若為有向圖則方向也相同）。邊的重?cái)?shù)：邊的重?cái)?shù)：兩頂點(diǎn)間平行邊的條數(shù)。兩頂點(diǎn)間平行邊的條數(shù)。多重圖：多重圖：含有平行邊的多重圖。含有平行邊的多重圖。自環(huán)（自回路）：自環(huán)（自回路）：兩個端點(diǎn)重合的邊兩個端點(diǎn)重合的邊簡單圖：簡單圖：不含平行邊且不含自環(huán)的圖。不含平行邊且不含自環(huán)的圖。13141v1v2v2v3v3v4v4v5v5v6v6v7v)(a)(b27253153551711227536415二、二、 圖中頂點(diǎn)的度數(shù)圖中頂點(diǎn)的度數(shù)1、無向圖中頂點(diǎn)的度數(shù)、無向圖中頂點(diǎn)的度數(shù)【定義【定義】在圖（無向圖或有向圖）中，

4、若頂點(diǎn)在圖（無向圖或有向圖）中，若頂點(diǎn)a和和b是邊是邊e的兩個端點(diǎn)，則稱頂點(diǎn)的兩個端點(diǎn)，則稱頂點(diǎn)a和和b是是鄰接鄰接的，并的，并稱邊稱邊e關(guān)聯(lián)關(guān)聯(lián)于頂點(diǎn)于頂點(diǎn)a和和b?！径x【定義】設(shè)圖設(shè)圖G是無向圖，是無向圖，v是圖是圖G中的頂點(diǎn)，與中的頂點(diǎn)，與v關(guān)聯(lián)的邊的條數(shù)稱為關(guān)聯(lián)的邊的條數(shù)稱為頂點(diǎn)頂點(diǎn)v的度數(shù)的度數(shù)，記作，記作deg(v)。 與結(jié)點(diǎn)與結(jié)點(diǎn)v關(guān)聯(lián)的環(huán)對關(guān)聯(lián)的環(huán)對v的度數(shù)的貢獻(xiàn)要計(jì)算兩次的度數(shù)的貢獻(xiàn)要計(jì)算兩次16孤立點(diǎn)：孤立點(diǎn)：度數(shù)為零的頂點(diǎn)度數(shù)為零的頂點(diǎn)懸掛點(diǎn)：懸掛點(diǎn)：度數(shù)為度數(shù)為1的頂點(diǎn)的頂點(diǎn)懸掛邊：懸掛邊：與懸掛點(diǎn)關(guān)聯(lián)的邊與懸掛點(diǎn)關(guān)聯(lián)的邊K度點(diǎn)：度點(diǎn)：度數(shù)為度數(shù)為k的頂點(diǎn)的頂點(diǎn)17【

5、定理定理】（握手定理）（握手定理） 任一圖中，頂點(diǎn)的度數(shù)的任一圖中，頂點(diǎn)的度數(shù)的總和等于邊數(shù)的二倍，即總和等于邊數(shù)的二倍，即【推論推論】 任一圖中，奇度數(shù)頂點(diǎn)的個數(shù)必為偶數(shù)。任一圖中，奇度數(shù)頂點(diǎn)的個數(shù)必為偶數(shù)。VvEv|2)(degVvVvVvEvvv|2)(deg)(deg)(deg211819【例【例】下列各組數(shù)中，哪下列各組數(shù)中，哪些些可以構(gòu)成無向圖的度可以構(gòu)成無向圖的度數(shù)列數(shù)列：（1） 1，1，1，2，2 （2） 2，2，2，2，3（3）2，3，3，3，3（4）2，2，2，2，2202122 23（2）有向圖中頂點(diǎn)的度數(shù)）有向圖中頂點(diǎn)的度數(shù)【定義【定義】設(shè)圖設(shè)圖G是有向圖，是有向圖，v

6、是是G的頂點(diǎn)，以的頂點(diǎn)，以v為始點(diǎn)為始點(diǎn)的有向邊的條數(shù)稱為的有向邊的條數(shù)稱為v的的出度出度，稱為，稱為deg+(v), 以以v為終為終點(diǎn)的有向邊的條數(shù)稱為點(diǎn)的有向邊的條數(shù)稱為v的的入度入度，稱為，稱為deg-(v)。例：例：deg+(a)=2 deg-(a)=1deg+(b)=0 deg-(b)=2deg+(c)=1 deg-(c)=2deg+(d)=2 deg-(d)=2deg+(e)=2 deg-(e)=024【定理定理】 設(shè)圖設(shè)圖G是有向圖，是有向圖，G中含有中含有n個頂點(diǎn)個頂點(diǎn)和和m條邊，則圖中各頂點(diǎn)的的出度之和與各頂條邊，則圖中各頂點(diǎn)的的出度之和與各頂點(diǎn)的入度之和相等，且等于圖的邊數(shù)

7、。點(diǎn)的入度之和相等，且等于圖的邊數(shù)。mvvVvVv)(deg)(deg-25三、特殊圖三、特殊圖 【定義【定義】設(shè)圖設(shè)圖G為無向簡單圖，如果圖為無向簡單圖，如果圖G中各個頂中各個頂點(diǎn)的度數(shù)都為點(diǎn)的度數(shù)都為k，則稱，則稱G為為k度度正則圖正則圖，記為，記為k-正正則圖則圖26三、特殊圖三、特殊圖 【定義【定義】在在n階無向簡單圖中，如果任意兩個不同的頂階無向簡單圖中，如果任意兩個不同的頂點(diǎn)之間都有一條邊關(guān)聯(lián)，則稱此無向簡單圖為點(diǎn)之間都有一條邊關(guān)聯(lián)，則稱此無向簡單圖為無向無向完全圖完全圖，記作，記作Kn。無向完全圖無向完全圖Kn的邊數(shù)是多少？的邊數(shù)是多少？ 【定理【定理】在在n階無向完全圖階無向完

8、全圖Kn中，共有中，共有n(n-1)/2條邊。條邊。27【定義【定義】在在n階有向圖中，如果任意兩個不同的頂點(diǎn)階有向圖中，如果任意兩個不同的頂點(diǎn)之間都有兩條方向相反的有向邊關(guān)聯(lián)，且每一個之間都有兩條方向相反的有向邊關(guān)聯(lián)，且每一個頂點(diǎn)都有自回路，則稱此有向圖為頂點(diǎn)都有自回路，則稱此有向圖為有向完全圖有向完全圖。有向完全圖各頂點(diǎn)的入度與出度是多少？有向完全圖各頂點(diǎn)的入度與出度是多少？三、特殊圖三、特殊圖 28四、四、 子圖子圖【定義【定義】在圖在圖G中刪去一些邊或頂點(diǎn)后所得的中刪去一些邊或頂點(diǎn)后所得的圖稱為圖圖稱為圖G的子圖。的子圖。刪邊：刪邊：刪去圖中某一條邊，但仍保留這條邊的兩個刪去圖中某一條

9、邊，但仍保留這條邊的兩個端點(diǎn)。端點(diǎn)。刪點(diǎn)：刪點(diǎn)：刪去圖中某一點(diǎn)以及與這個點(diǎn)關(guān)聯(lián)的所有邊。刪去圖中某一點(diǎn)以及與這個點(diǎn)關(guān)聯(lián)的所有邊。29刪邊刪邊刪點(diǎn)刪點(diǎn)30【定義【定義】由圖由圖G中刪去一些邊后所得到的子圖稱為中刪去一些邊后所得到的子圖稱為圖圖G的的生成子圖生成子圖?！径x】在圖【定義】在圖G中僅刪去一個頂點(diǎn)后所得的子圖稱中僅刪去一個頂點(diǎn)后所得的子圖稱為圖為圖G的的主子圖主子圖。313233設(shè)有兩個圖設(shè)有兩個圖G1=(V1, E1)，G2=(V2, E2)，如果存在著如果存在著雙射雙射 ：V1V2，使得，使得(u,v)E1當(dāng)且僅當(dāng)當(dāng)且僅當(dāng) ( (u), (v)E2 且邊的重?cái)?shù)相同，則稱圖且邊的重?cái)?shù)

10、相同，則稱圖G1與與G2同構(gòu)同構(gòu)，記作記作 G1 G2。3435363738注意：注意：頂點(diǎn)數(shù)相同、邊數(shù)相同、度數(shù)列相同頂點(diǎn)數(shù)相同、邊數(shù)相同、度數(shù)列相同為二圖同構(gòu)的必要條件而非充分條件為二圖同構(gòu)的必要條件而非充分條件391 12 25 56 63 34 4Ga ab be ef fc cd dG40 41六、補(bǔ)圖六、補(bǔ)圖 【定義定義】 G為為n階簡單圖，由階簡單圖，由G的所有頂點(diǎn)和的所有頂點(diǎn)和能使能使G成為完全圖的添加邊所構(gòu)成的圖稱為成為完全圖的添加邊所構(gòu)成的圖稱為G的相的相對于完全圖的對于完全圖的補(bǔ)圖補(bǔ)圖，簡稱，簡稱G的補(bǔ)圖，記作的補(bǔ)圖，記作 。 G42【例【例】 下圖中下圖中 是是G相對于

11、相對于K5的補(bǔ)圖。的補(bǔ)圖。G43 對于補(bǔ)圖對于補(bǔ)圖,顯然有以下結(jié)論顯然有以下結(jié)論GGGG 互為補(bǔ)圖，即互為補(bǔ)圖，即與與)1( )()()()()()2(GEGEKEGEGEn(3) n階完全圖與階完全圖與n階零圖互為補(bǔ)圖階零圖互為補(bǔ)圖44第2節(jié) 圖的連通性45 成都成都昆明昆明重慶重慶廣州廣州長沙長沙武漢武漢上海上海蘭州蘭州西安西安沈陽沈陽北京北京天津天津鄭州鄭州廈門廈門高雄高雄臺北臺北46471v1v2v2v3v3v4v1e1e2e2e3e3e4e4e5e5e6e7e4849 5051原岸原岸對岸對岸 原岸原岸對岸對岸 初始初始狀態(tài)狀態(tài)結(jié)束結(jié)束狀態(tài)狀態(tài)渡河過程中所有可能的安全狀態(tài)：渡河過程中

12、所有可能的安全狀態(tài)：可以使用二元組表示安全狀態(tài)：第一元素表示留可以使用二元組表示安全狀態(tài)：第一元素表示留在原岸的子集，第二元素表示留在對岸的子集。在原岸的子集，第二元素表示留在對岸的子集。52531）起點(diǎn)與終點(diǎn)相同的通路）起點(diǎn)與終點(diǎn)相同的通路(長度長度 1)稱為稱為回路回路(circuit)。2）邊不重復(fù)的回路稱為）邊不重復(fù)的回路稱為簡單回路簡單回路。3）除起點(diǎn)重復(fù)一次外）除起點(diǎn)重復(fù)一次外, 別的結(jié)點(diǎn)均不重別的結(jié)點(diǎn)均不重復(fù)的復(fù)的簡單回路簡單回路稱為稱為基本回路基本回路或或環(huán)環(huán)(cycle)。540v0v55 56 575859 6061 【定義定義】設(shè)圖設(shè)圖G是無向連通圖，如果圖是無向連通圖，

13、如果圖G中存在一個頂中存在一個頂點(diǎn)點(diǎn)v，使得刪去頂點(diǎn)，使得刪去頂點(diǎn)v后，圖后，圖G成為不連通圖，則稱成為不連通圖，則稱v為為割點(diǎn)割點(diǎn)。 【定義定義】設(shè)圖設(shè)圖G是無向連通圖，如果圖是無向連通圖，如果圖G中存在一條邊中存在一條邊u，使得刪去邊，使得刪去邊u后，圖后，圖G成為不連通圖，則稱成為不連通圖，則稱v為為割割邊或橋邊或橋。62 【定義定義】在簡單有向圖在簡單有向圖G中，若任二頂點(diǎn)間均相互可達(dá)，中，若任二頂點(diǎn)間均相互可達(dá)，則稱則稱G為為強(qiáng)連通圖強(qiáng)連通圖；若任二頂點(diǎn)間至少從一個頂點(diǎn)到；若任二頂點(diǎn)間至少從一個頂點(diǎn)到另一個頂點(diǎn)是可達(dá)的，則稱另一個頂點(diǎn)是可達(dá)的，則稱G是是單向連通圖單向連通圖；若在忽；

14、若在忽略略G中各邊的方向時中各邊的方向時G是無向連通圖，則稱是無向連通圖，則稱G是是弱連弱連通圖通圖。 63 【例例】下下圖中，圖圖中，圖(a)是強(qiáng)連通圖，圖是強(qiáng)連通圖，圖(b)是單是單向連通圖，圖向連通圖，圖(c)是弱連通圖。是弱連通圖。abcdabcdabcd64第3節(jié) 圖的表示65 【定義定義】設(shè)無向圖設(shè)無向圖G的點(diǎn)集為的點(diǎn)集為V，邊集為，邊集為E，且，且V=v1，v2，vn，E=e1,e2,em,令令則稱則稱(m ij ) nm 為為G的關(guān)聯(lián)矩陣，記作的關(guān)聯(lián)矩陣，記作 M (G) 的的環(huán)環(huán)是是關(guān)關(guān)聯(lián)聯(lián)關(guān)關(guān)聯(lián)聯(lián)與與不不關(guān)關(guān)聯(lián)聯(lián)與與ijijijijvevevem21066【例例】 求下圖求

15、下圖G的關(guān)聯(lián)矩陣。的關(guān)聯(lián)矩陣。12342100001110( )0011100001M G12345eeeee67 無向圖的關(guān)聯(lián)矩陣的特性：無向圖的關(guān)聯(lián)矩陣的特性： （1） ，即，即 M(G)每每列元素之和為列元素之和為2，因?yàn)槊織l邊恰有兩個端點(diǎn)，因?yàn)槊織l邊恰有兩個端點(diǎn)（若是簡單圖則每列恰有兩個（若是簡單圖則每列恰有兩個1）。）。 （2） ，因而全為，因而全為0的行所的行所對應(yīng)的頂點(diǎn)是孤立頂點(diǎn)。對應(yīng)的頂點(diǎn)是孤立頂點(diǎn)。12(1,2,)nijimjm mjiijvdm1)(68 * 4、有向無環(huán)圖的關(guān)聯(lián)矩陣、有向無環(huán)圖的關(guān)聯(lián)矩陣 【定義定義】設(shè)設(shè)G=V,E是有向無環(huán)圖，是有向無環(huán)圖， V=v1，v

16、2，vn，E=e1，e2，em，令，令101ijmvi是是ej的起點(diǎn)的起點(diǎn) vi與與ej不關(guān)聯(lián)不關(guān)聯(lián) vi是是ej的終點(diǎn)的終點(diǎn) 則稱則稱(m ij ) nn 為為G的關(guān)聯(lián)矩陣，記作的關(guān)聯(lián)矩陣，記作 M (G)。 6912345100000111100( )011011000111000000M G123456eeeeee70 M (G) 的特性：的特性： （1） （一條邊關(guān)聯(lián)兩個點(diǎn)：一個起點(diǎn)，一（一條邊關(guān)聯(lián)兩個點(diǎn)：一個起點(diǎn)，一個終點(diǎn)），從而有個終點(diǎn)），從而有 。 （2）每一行中）每一行中1的數(shù)目是該點(diǎn)的出度，的數(shù)目是該點(diǎn)的出度，-1的數(shù)目是該的數(shù)目是該點(diǎn)的入度。點(diǎn)的入度。 （3）二列相同，當(dāng)且

17、僅當(dāng)對應(yīng)的邊是平行邊（同向）。）二列相同，當(dāng)且僅當(dāng)對應(yīng)的邊是平行邊（同向）。 （4）全為）全為0的行對應(yīng)孤立頂點(diǎn)。的行對應(yīng)孤立頂點(diǎn)。10nijim110mnijjim 71 注注:無向圖也有相應(yīng)的鄰接矩陣，一般只考無向圖也有相應(yīng)的鄰接矩陣，一般只考慮簡單圖，無向圖的鄰接矩陣是對稱的，其性慮簡單圖，無向圖的鄰接矩陣是對稱的，其性質(zhì)基本與有向圖鄰接矩陣的性質(zhì)相同。質(zhì)基本與有向圖鄰接矩陣的性質(zhì)相同。72731v1v2v2v3v3v4v4v1G2G,0110110110020120)(1GA.0100010110000020)(2GA無向圖中自環(huán)對應(yīng)主對角線上元素是無向圖中自環(huán)對應(yīng)主對角線上元素是1還

18、是還是2？747576nivaaaaiiiiijjiiij,.,2 , 1),deg(n1n177練習(xí)現(xiàn)有如下所示圖：(1) 寫出該圖的關(guān)聯(lián)矩陣和鄰接矩陣。(2) 求各個頂點(diǎn)的度。(3) 圖中是否存在平行邊？如果存在，請指出。 78jviv1v2vnv791v2v3v4v5v8081828311121212211212.( ).nnnnnnnrrrrrrR GAAArrr841v2v3v4v5v858687第第4節(jié)節(jié) 一些特殊的圖一些特殊的圖881 二部圖【定義【定義】無向圖無向圖G=V，E的頂點(diǎn)集的頂點(diǎn)集V能分成兩個能分成兩個子集子集V1和和V2，滿足，滿足（1）V=V1V2，V1V2= ；

19、（2）任給）任給e=（u，v）E，均有，均有uV1，vV2。則稱則稱G為二部圖。為二部圖?！径x【定義】設(shè)設(shè)G = (V, E)是二部圖，如果是二部圖，如果V1中每個頂點(diǎn)中每個頂點(diǎn)都與都與V2中所有頂點(diǎn)鄰接，則稱中所有頂點(diǎn)鄰接，則稱G為完全二部圖，并為完全二部圖，并記為記為Km,n，其中，其中m=|V1|，n=|V2|。Km,n的邊數(shù)是多少？的邊數(shù)是多少？89Km,n的邊數(shù)是多少？的邊數(shù)是多少？90一個無向圖是二部圖當(dāng)且僅當(dāng)一個無向圖是二部圖當(dāng)且僅當(dāng)圖中無奇數(shù)長度的回路。圖中無奇數(shù)長度的回路。9192（補(bǔ)）二部圖的應(yīng)用（補(bǔ)）二部圖的應(yīng)用某公司招聘了某公司招聘了3名大學(xué)畢業(yè)生，公司有名大學(xué)畢業(yè)生

20、，公司有5個部門需要個部門需要人。不考慮單向的意愿，畢業(yè)生意愿去這個部門，人。不考慮單向的意愿，畢業(yè)生意愿去這個部門，這個部門也同意接收這名畢業(yè)生如表所示。這個部門也同意接收這名畢業(yè)生如表所示。部門部門1部門部門2部門部門3部門部門4部門部門5畢業(yè)生畢業(yè)生A*畢業(yè)生畢業(yè)生B*畢業(yè)生畢業(yè)生C*有什么分配方案使得在每個部門最多可接收一有什么分配方案使得在每個部門最多可接收一個畢業(yè)生的前提下畢業(yè)生都滿意！個畢業(yè)生的前提下畢業(yè)生都滿意！93 94 95961v2v3v4v5v9798abcde99100v v1 1v v2 2v v3 3v v4 4v v5 5(b)(b)v v1 1v v2 2v

21、v3 3v v4 4(c)(c)v v1 1v v2 2v v3 3v v4 4v v5 5(a)(a)101 A(甲)B(乙)C102 103104)(a)(bbcade1v2v3v4v5v105106107 108上述定理在應(yīng)用中它本身用處不大，但上述定理在應(yīng)用中它本身用處不大，但它的逆否命題卻非常有用。我們經(jīng)常利它的逆否命題卻非常有用。我們經(jīng)常利用其逆否命題來判斷某些圖不是漢密爾用其逆否命題來判斷某些圖不是漢密爾頓圖，即：頓圖，即： 若存在若存在V的某個非空子集的某個非空子集W使得使得w(G-W)|W|，則，則G不是漢密爾頓圖。不是漢密爾頓圖。109110v v3 3v v1 1v v2

22、 2v v4 4v v5 5v v6 6v v7 7v v2 2v v4 4v v1 1v v5 5v v3 3111設(shè)設(shè)G = (V, E)是是n(n 3)階階簡單無向圖簡單無向圖, 若對于任意的不相鄰結(jié)點(diǎn)若對于任意的不相鄰結(jié)點(diǎn)u, v V, 有有 1121v2v3v4v5v6v113114設(shè)設(shè)G = (V, E)是是n(n 3)階簡單無向圖階簡單無向圖, 若對于任意的不相鄰結(jié)點(diǎn)若對于任意的不相鄰結(jié)點(diǎn)u, v V, 有有在在 中存在中存在 115116 117第5節(jié) 最短路徑1181 Dijkstra算法算法1191v2v3v4v5v6v4233321120121122基本思想基本思想：設(shè)置

23、一個集合：設(shè)置一個集合S（也可以看作紅點(diǎn)集）（也可以看作紅點(diǎn)集）存存放已經(jīng)找到最短路徑的頂點(diǎn)，放已經(jīng)找到最短路徑的頂點(diǎn)，S的初始狀態(tài)只包含源的初始狀態(tài)只包含源點(diǎn)點(diǎn)v，對，對viV- -S （也可以看作藍(lán)點(diǎn)集）（也可以看作藍(lán)點(diǎn)集） ，假設(shè)從源，假設(shè)從源點(diǎn)點(diǎn)v到到vi的有向邊為最短路徑。以后每求得一條最短的有向邊為最短路徑。以后每求得一條最短路徑路徑v, , vk，就將，就將vk加入集合加入集合S中，并將路徑中，并將路徑v, , vk , vi與原來的假設(shè)相比較，取路徑長度較小者為最與原來的假設(shè)相比較，取路徑長度較小者為最短路徑。重復(fù)上述過程，直到集合短路徑。重復(fù)上述過程，直到集合V中全部頂點(diǎn)加中全部頂點(diǎn)加入到集合入到集合S中。中。1 Dijkstra算法算法123 集集 合合 V- -S集集合合 Svkv