1、 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 1Email: 圖論及其應(yīng)用圖論及其應(yīng)用任課教師：楊春任課教師：楊春數(shù)學(xué)科學(xué)學(xué)院數(shù)學(xué)科學(xué)學(xué)院 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 2第三章第三章 圖的連通性圖的連通性主要內(nèi)容主要內(nèi)容一、割邊、割點(diǎn)和塊一、割邊、割點(diǎn)和塊二、圖的連通度與敏格爾定理二、圖的連通度與敏格爾定理三、圖的寬直徑簡(jiǎn)介三、圖的寬直徑簡(jiǎn)介教學(xué)時(shí)數(shù)教學(xué)時(shí)數(shù)安排安排6學(xué)時(shí)講授本章內(nèi)容學(xué)時(shí)講授本章內(nèi)容圖的連通性刻畫(huà)圖的連通性刻畫(huà) 0.8 1 0.6 0.

2、4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 3本次課主要內(nèi)容本次課主要內(nèi)容(一一)、割邊及其性質(zhì)、割邊及其性質(zhì)(二二)、割點(diǎn)及其性質(zhì)、割點(diǎn)及其性質(zhì)(三三)、塊及其性質(zhì)、塊及其性質(zhì)割邊、割點(diǎn)和塊割邊、割點(diǎn)和塊 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 4研究圖的連通性的意義研究圖的連通性的意義 研究圖的連通性，主要研究圖的連通程度的刻畫(huà)，研究圖的連通性，主要研究圖的連通程度的刻畫(huà)，其意義是：其意義是： 圖論意義：圖的連通程度的高低，是圖結(jié)構(gòu)性質(zhì)的重圖論意義：圖的連通程度的高低，是圖結(jié)構(gòu)性質(zhì)的

3、重要表征，圖的許多性質(zhì)都與其相關(guān)，例如：連通圖中任要表征，圖的許多性質(zhì)都與其相關(guān)，例如：連通圖中任意兩點(diǎn)間不相交路的條數(shù)就與圖的連通程度有關(guān)。意兩點(diǎn)間不相交路的條數(shù)就與圖的連通程度有關(guān)。 實(shí)際意義：圖的連通程度的高低，對(duì)應(yīng)于通信網(wǎng)絡(luò)實(shí)際意義：圖的連通程度的高低，對(duì)應(yīng)于通信網(wǎng)絡(luò)“可靠性程度可靠性程度”的高低。的高低。 網(wǎng)絡(luò)可靠性，是指網(wǎng)絡(luò)運(yùn)作的好壞程度，即指如計(jì)算網(wǎng)絡(luò)可靠性，是指網(wǎng)絡(luò)運(yùn)作的好壞程度，即指如計(jì)算機(jī)網(wǎng)絡(luò)、通信網(wǎng)絡(luò)等對(duì)某個(gè)組成部分崩潰的容忍程度。機(jī)網(wǎng)絡(luò)、通信網(wǎng)絡(luò)等對(duì)某個(gè)組成部分崩潰的容忍程度。 網(wǎng)絡(luò)可靠性，網(wǎng)絡(luò)可靠性， 是用可靠性參數(shù)來(lái)描述的。參數(shù)主要是用可靠性參數(shù)來(lái)描述的。參數(shù)主要分

4、確定性參數(shù)與概率性參數(shù)。分確定性參數(shù)與概率性參數(shù)。 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 5 確定性參數(shù)主要考慮網(wǎng)絡(luò)在最壞情況下的可靠性度確定性參數(shù)主要考慮網(wǎng)絡(luò)在最壞情況下的可靠性度量，常稱(chēng)為網(wǎng)絡(luò)拓?fù)涞牧浚７Q(chēng)為網(wǎng)絡(luò)拓?fù)涞摹叭蒎e(cuò)性度量容錯(cuò)性度量”，通常用圖論概，通常用圖論概念給出，其中，本章將介紹的圖的連通度就是網(wǎng)絡(luò)確定念給出，其中，本章將介紹的圖的連通度就是網(wǎng)絡(luò)確定性參數(shù)之一。近年來(lái)，人們又提出了性參數(shù)之一。近年來(lái)，人們又提出了“堅(jiān)韌度堅(jiān)韌度”、“核核度度”、“整度整度”等描述網(wǎng)絡(luò)容錯(cuò)性的參數(shù)。等描述網(wǎng)絡(luò)容錯(cuò)性的參數(shù)。 概

5、率性參數(shù)主要考慮網(wǎng)絡(luò)中處理器與信關(guān)以隨機(jī)的、概率性參數(shù)主要考慮網(wǎng)絡(luò)中處理器與信關(guān)以隨機(jī)的、彼此獨(dú)立的按某種確定性概率損壞的情況下，網(wǎng)絡(luò)的可彼此獨(dú)立的按某種確定性概率損壞的情況下，網(wǎng)絡(luò)的可靠性度量，常稱(chēng)為網(wǎng)絡(luò)拓?fù)涞目啃远攘?，常稱(chēng)為網(wǎng)絡(luò)拓?fù)涞摹翱煽啃远攘靠煽啃远攘俊薄?一一)、割邊及其性質(zhì)、割邊及其性質(zhì) 定義定義1 邊邊e為圖為圖G的一條割邊，如果的一條割邊，如果 。()()GeG紅色邊為該圖的割邊紅色邊為該圖的割邊 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 6 注：割邊又稱(chēng)為圖的注：割邊又稱(chēng)為圖的“橋橋”。 圖的割邊有如下性質(zhì)：圖

6、的割邊有如下性質(zhì)： 定理定理1 邊邊 e 是圖是圖G的割邊當(dāng)且僅當(dāng)?shù)母钸叜?dāng)且僅當(dāng) e 不在不在G的任何圈中。的任何圈中。 證明：可以假設(shè)證明：可以假設(shè)G連通。連通。 若不然。設(shè)若不然。設(shè) e 在圖在圖G的某圈的某圈 C 中，且令中，且令e = u v. 考慮考慮P = C- e,則則P是一條是一條u v路。下面證明路。下面證明G-e連通。連通。 對(duì)任意對(duì)任意 x, y V(G-e) ，由于，由于G連通，所以存在連通，所以存在x -y路路Q(chēng).若若Q不含不含e，則，則x與與y在在G-e里連通；若里連通；若Q含有含有e，則可，則可選擇路：選擇路：x -u P v - y,說(shuō)明說(shuō)明x與與y在在G-e里

7、也連通。所以里也連通。所以,若邊若邊e在在G的某圈中，則的某圈中，則G-e連通。連通。 但這與但這與e是是G的割邊矛盾！的割邊矛盾！ “必要性必要性” 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 7 “充分性充分性” 如果如果e不是不是G的割邊，則的割邊，則G-e連通，于是在連通，于是在G-e中存在中存在一條一條u - v 路，顯然：該路并上邊路，顯然：該路并上邊e得到得到G中一個(gè)包含邊中一個(gè)包含邊e的圈，矛盾。的圈，矛盾。 推論推論1 e為連通圖為連通圖G的一條邊，如果的一條邊，如果e含于含于G的某圈中，的某圈中，則則G-e連通

8、。連通。 證明：若不然，證明：若不然，G-e不連通，于是不連通，于是e是割邊。由定理是割邊。由定理1，e不在不在G的任意圈中，矛盾！的任意圈中，矛盾！ 例例1 求證求證: (1) 若若G的每個(gè)頂點(diǎn)的度數(shù)均為偶數(shù)，則的每個(gè)頂點(diǎn)的度數(shù)均為偶數(shù)，則G沒(méi)有割邊沒(méi)有割邊; (2) 若若G為為k正則二部圖正則二部圖(k2)2)，則，則G G無(wú)割邊。無(wú)割邊。 證明證明: (1)若不然，設(shè)若不然，設(shè)e=uv 為為G的割邊。則的割邊。則G-e的含有的含有頂點(diǎn)頂點(diǎn)u(或或v)的那個(gè)分支中點(diǎn)的那個(gè)分支中點(diǎn)u(或或v)的度數(shù)為奇，而其余點(diǎn)的度數(shù)為奇，而其余點(diǎn)的度數(shù)為偶數(shù)，與握手定理推論相矛盾！的度數(shù)為偶數(shù)，與握手定理

9、推論相矛盾！ 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 8 (2)若不然，設(shè)若不然，設(shè)e=uv 為為G的割邊。取的割邊。取G-e的其中一個(gè)分的其中一個(gè)分支支G1, 顯然，顯然，G1中只有一個(gè)頂點(diǎn)的度數(shù)是中只有一個(gè)頂點(diǎn)的度數(shù)是k-1,其余點(diǎn)的度其余點(diǎn)的度數(shù)為數(shù)為k。并且。并且G1仍然為偶圖。仍然為偶圖。 假若假若G1的兩個(gè)頂點(diǎn)子集包含的頂點(diǎn)數(shù)分別為的兩個(gè)頂點(diǎn)子集包含的頂點(diǎn)數(shù)分別為m與與n，并且包含并且包含m個(gè)頂點(diǎn)的頂點(diǎn)子集包含度為個(gè)頂點(diǎn)的頂點(diǎn)子集包含度為k-1的那個(gè)點(diǎn)，那的那個(gè)點(diǎn)，那么有：么有：k m-1= k n。但是因。但是因

10、k22，所以等式不能成立！，所以等式不能成立！(二二)、割點(diǎn)及其性質(zhì)、割點(diǎn)及其性質(zhì) 定義定義7 在在G中，如果中，如果E(G)可以劃分為兩個(gè)非空子集可以劃分為兩個(gè)非空子集E1與與E2,使使GE1和和GE2以點(diǎn)以點(diǎn)v為公共頂點(diǎn)，稱(chēng)為公共頂點(diǎn)，稱(chēng)v為為G的一個(gè)的一個(gè)割點(diǎn)。割點(diǎn)。 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 9 在圖在圖G1中，點(diǎn)中，點(diǎn)v1, v4，v3均是割點(diǎn)；在均是割點(diǎn)；在G2中，中，v5是割點(diǎn)。是割點(diǎn)。v1v2v3v4e3e1e2e4e5e6圖圖G1v1v3v2v4v5圖圖G2 定理定理2 G無(wú)環(huán)且非平凡，則無(wú)環(huán)且

11、非平凡，則v是是G的割點(diǎn)，當(dāng)且僅當(dāng)?shù)母铧c(diǎn)，當(dāng)且僅當(dāng)()()GvG 證明：證明：“必要性必要性” 設(shè)設(shè)v是是G的割點(diǎn)。則的割點(diǎn)。則E(G)可劃分為兩個(gè)非空邊子集可劃分為兩個(gè)非空邊子集E1與與E2,使使GE1,GE2恰好以恰好以v為公共點(diǎn)。由于為公共點(diǎn)。由于G沒(méi)有環(huán)，沒(méi)有環(huán)，所所 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 10以，以，GE1,GE2分別至少包含異于分別至少包含異于v的的G的點(diǎn)，這樣，的點(diǎn)，這樣，G-v的分支數(shù)比的分支數(shù)比G的分支數(shù)至少多的分支數(shù)至少多1，所以：，所以：()()GvG “充分性充分性” 由割點(diǎn)定義結(jié)論顯

12、然。由割點(diǎn)定義結(jié)論顯然。 定理定理3 v是樹(shù)是樹(shù)T的頂點(diǎn)，則的頂點(diǎn)，則v是割點(diǎn)，當(dāng)且僅當(dāng)是割點(diǎn)，當(dāng)且僅當(dāng)v是樹(shù)的是樹(shù)的分支點(diǎn)。分支點(diǎn)。 證明：證明：“必要性必要性” 若不然，有若不然，有d (v)=1,即即v是樹(shù)葉，顯然不能是割點(diǎn)。是樹(shù)葉，顯然不能是割點(diǎn)。 “充分性充分性” 設(shè)設(shè)v是分支點(diǎn)，則是分支點(diǎn)，則d (v)1.于是設(shè)于是設(shè)x與與y是是v的鄰點(diǎn)，由的鄰點(diǎn)，由樹(shù)的性質(zhì)，只有唯一路連接樹(shù)的性質(zhì)，只有唯一路連接x與與y，所以，所以G-v分離分離x與與y .即即v為割點(diǎn)。為割點(diǎn)。 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 11 定

13、理定理4 設(shè)設(shè)v是無(wú)環(huán)連通圖是無(wú)環(huán)連通圖G的一個(gè)頂點(diǎn)，則的一個(gè)頂點(diǎn)，則v是是G的割的割點(diǎn)，當(dāng)且僅當(dāng)點(diǎn)，當(dāng)且僅當(dāng)V(G-v)可以劃分為兩個(gè)非空子集可以劃分為兩個(gè)非空子集V1與與V2,使使得對(duì)任意得對(duì)任意x V1, y V2, 點(diǎn)點(diǎn)v在每一條在每一條x y路上。路上。 證明：證明：“必要性必要性” v是無(wú)環(huán)連通圖是無(wú)環(huán)連通圖G的割點(diǎn)，由定理的割點(diǎn)，由定理2，G-v至少有兩個(gè)至少有兩個(gè)連通分支。設(shè)其中一個(gè)連通分支頂點(diǎn)集合為連通分支。設(shè)其中一個(gè)連通分支頂點(diǎn)集合為V1,另外連通另外連通分支頂點(diǎn)集合為分支頂點(diǎn)集合為V2,即即V1與與V2構(gòu)成構(gòu)成V的劃分。的劃分。 “充分性充分性” 對(duì)于任意的對(duì)于任意的x

14、V1, y V2，如果點(diǎn)，如果點(diǎn)v不在某一條不在某一條xy路路上，那么，該路也是連接上，那么，該路也是連接G-v中的中的x與與y的路，這與的路，這與x,y處處于于G-v的不同分支矛盾。的不同分支矛盾。 若若v不是圖不是圖G的割點(diǎn)，那么的割點(diǎn)，那么G-v連通，因此在連通，因此在G-v中存在中存在x,y路，當(dāng)然也是路，當(dāng)然也是G中一條沒(méi)有經(jīng)過(guò)點(diǎn)中一條沒(méi)有經(jīng)過(guò)點(diǎn)v的的x,y路。矛盾。路。矛盾。 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 12 例例2 求證：無(wú)環(huán)非平凡連通圖至少有兩個(gè)非割點(diǎn)。求證：無(wú)環(huán)非平凡連通圖至少有兩個(gè)非割點(diǎn)。 證明

15、：證明： 由于由于G是無(wú)環(huán)非平凡連通圖，所以存在非平是無(wú)環(huán)非平凡連通圖，所以存在非平凡生成樹(shù)，而非平凡生成樹(shù)至少兩片樹(shù)葉，它不能為割凡生成樹(shù)，而非平凡生成樹(shù)至少兩片樹(shù)葉，它不能為割點(diǎn)，所以，它也不能為點(diǎn)，所以，它也不能為G的割點(diǎn)。的割點(diǎn)。 證明：設(shè)證明：設(shè)T是是G的一棵生成樹(shù)。由于的一棵生成樹(shù)。由于G有有n-2個(gè)割點(diǎn)，個(gè)割點(diǎn)，所以，所以，T有有n-2個(gè)割點(diǎn)，即個(gè)割點(diǎn)，即T只有兩片樹(shù)葉，所以只有兩片樹(shù)葉，所以T是一條是一條路。這說(shuō)明，路。這說(shuō)明，G的任意生成樹(shù)為路。的任意生成樹(shù)為路。 例例3 求證：恰有兩個(gè)非割點(diǎn)的連通單圖是一條路。求證：恰有兩個(gè)非割點(diǎn)的連通單圖是一條路。 一個(gè)單圖的任意生成樹(shù)為

16、路，則該圖為圈或路，若為一個(gè)單圖的任意生成樹(shù)為路，則該圖為圈或路，若為圈，則圈，則G沒(méi)有割點(diǎn)，矛盾，所以，沒(méi)有割點(diǎn)，矛盾，所以，G為路。為路。 例例4 求證：若求證：若v是單圖是單圖G的割點(diǎn)，則它不是的割點(diǎn)，則它不是G的補(bǔ)圖的的補(bǔ)圖的割點(diǎn)。割點(diǎn)。 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 13 證明：證明： v是單圖是單圖G的割點(diǎn)，則的割點(diǎn)，則G-v至少兩個(gè)連通分支。至少兩個(gè)連通分支?，F(xiàn)任取現(xiàn)任取 , 如果如果x,y在在G-v的同一分支中，令的同一分支中，令u是是與與x,y處于不同分支的點(diǎn)，那么，通過(guò)處于不同分支的點(diǎn)，那么，通過(guò)

17、u，可說(shuō)明，可說(shuō)明，x與與y在在G-v的補(bǔ)圖中連通。若的補(bǔ)圖中連通。若x,y在在G-v的不同分支中，則它們的不同分支中，則它們?cè)谠贕-v的補(bǔ)圖中鄰接。所以，若的補(bǔ)圖中鄰接。所以，若v是是G的割點(diǎn)，則的割點(diǎn)，則v不是其不是其補(bǔ)圖的割點(diǎn)。補(bǔ)圖的割點(diǎn)。,()x yV Gv(三三)、塊及其性質(zhì)、塊及其性質(zhì) 定義定義8 沒(méi)有割點(diǎn)的連通圖稱(chēng)為是一個(gè)塊圖，簡(jiǎn)稱(chēng)塊；沒(méi)有割點(diǎn)的連通圖稱(chēng)為是一個(gè)塊圖，簡(jiǎn)稱(chēng)塊；G的一個(gè)子圖的一個(gè)子圖B稱(chēng)為是稱(chēng)為是G的一個(gè)塊，如果的一個(gè)塊，如果(1), 它本身是塊；它本身是塊；(2), 若沒(méi)有真包含若沒(méi)有真包含B的的G的塊存在。的塊存在。 例例7 找出下圖找出下圖G中的所有塊。中的所

18、有塊。 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 14 解：由塊的定義得：解：由塊的定義得：圖圖G 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 15 定理定理5 若若|V(G)|3,3,則則G G是塊，當(dāng)且僅當(dāng)是塊，當(dāng)且僅當(dāng)G G無(wú)環(huán)且任意無(wú)環(huán)且任意兩頂點(diǎn)位于同一圈上。兩頂點(diǎn)位于同一圈上。 證明：證明：(必要性）設(shè)必要性）設(shè)G是塊。因是塊。因G沒(méi)有割點(diǎn)，所以，它沒(méi)有割點(diǎn)，所以，它不能有環(huán)。對(duì)任意不能有環(huán)。對(duì)任意u, v V(G),下面證明下面證明u, v位于某一圈位

19、于某一圈上。上。 對(duì)對(duì)d (u, v) 作數(shù)學(xué)歸納法證明。作數(shù)學(xué)歸納法證明。 當(dāng)當(dāng)d (u, v) =1時(shí)，由于時(shí)，由于G是至少是至少3個(gè)點(diǎn)的塊，所以，邊個(gè)點(diǎn)的塊，所以，邊uv不能為割邊，否則，不能為割邊，否則，u或或v為割點(diǎn)，矛盾。由割邊性質(zhì)，為割點(diǎn)，矛盾。由割邊性質(zhì)，uv必然在某圈中。必然在某圈中。 設(shè)當(dāng)設(shè)當(dāng)d (u, v) k時(shí)結(jié)論成立。時(shí)結(jié)論成立。 設(shè)設(shè)d (u, v) =k。 設(shè)設(shè)P是一條最短是一條最短(u, v)路，路，w是是v前面一點(diǎn)，則前面一點(diǎn)，則d (u, w) =k-1 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1

20、n 16 由歸納假設(shè)，由歸納假設(shè)，u與與w在同一圈在同一圈C =P1PP2 2上。上。uwvPP2P1 考慮考慮G-w. 由于由于G是塊，所以是塊，所以G-w連通。設(shè)連通。設(shè)Q是一條在是一條在G-w中的中的(u, v)路，并且設(shè)它與路，并且設(shè)它與C的最后一個(gè)交點(diǎn)為的最后一個(gè)交點(diǎn)為x。uwvQP2P1x 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 17 則則uP1xvwP2為包含為包含u, v的圈。的圈。 (充分性充分性)：若：若G不是塊，則不是塊，則G中有割點(diǎn)中有割點(diǎn)v。由于。由于G無(wú)環(huán)，所無(wú)環(huán)，所以以G-v至少兩個(gè)分支。設(shè)至少兩

21、個(gè)分支。設(shè)x, y是是G-v的兩個(gè)不同分支中的點(diǎn)，的兩個(gè)不同分支中的點(diǎn)，則則x, y在在G中不能位于同一圈上，矛盾！中不能位于同一圈上，矛盾！ 定理定理6 點(diǎn)點(diǎn)v是圖是圖G的割點(diǎn)當(dāng)且僅當(dāng)?shù)母铧c(diǎn)當(dāng)且僅當(dāng)v至少屬于至少屬于G的兩個(gè)不的兩個(gè)不同的塊。同的塊。 證明：證明：(必要性必要性) 設(shè)設(shè)v是是G的割點(diǎn)。由割點(diǎn)定義：的割點(diǎn)。由割點(diǎn)定義：E(G)可以可以劃分為兩個(gè)邊子集劃分為兩個(gè)邊子集E1與與E2。顯然。顯然GE1與與GE2有唯一公共頂有唯一公共頂點(diǎn)點(diǎn)v。設(shè)。設(shè)B1與與B2分別是分別是GE1和和GE2中包含中包含v的塊，顯然它們的塊，顯然它們也是也是G的塊。即證明的塊。即證明v至少屬于至少屬于G的

22、兩個(gè)不同塊。的兩個(gè)不同塊。 (充分性充分性) 如果如果v屬于屬于G的兩個(gè)不同塊，我們證明：的兩個(gè)不同塊，我們證明：v 一定一定是圖是圖G的割點(diǎn)。的割點(diǎn)。 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 18 如果包含如果包含v的其中一個(gè)塊是環(huán)，顯然的其中一個(gè)塊是環(huán)，顯然v是割點(diǎn)；是割點(diǎn)； 設(shè)包含設(shè)包含v的兩個(gè)塊是的兩個(gè)塊是B1與與B2。如果包含。如果包含v的兩個(gè)塊不是環(huán)，的兩個(gè)塊不是環(huán)，那么兩個(gè)塊分別至少有兩個(gè)頂點(diǎn)。假如那么兩個(gè)塊分別至少有兩個(gè)頂點(diǎn)。假如v不是割點(diǎn)，在不是割點(diǎn)，在B1與與B2中分別找異于中分別找異于v的一個(gè)點(diǎn)的一個(gè)點(diǎn)x與與y, x V(B1), y V(B2),則在則在G-v中有連接中有連接x與與y的路的路P。 顯然：顯然：B1BB2 2PP無(wú)