圖論第三章圖的連通性

圖論課件第三章圖的連通性1第1頁(yè)，本講稿共29頁(yè)第三章圖的連通性主要內(nèi)容一、割邊、割點(diǎn)和塊二、圖的連通度與敏格爾定理三、圖的寬直徑簡(jiǎn)介教學(xué)時(shí)數(shù)安排6學(xué)時(shí)講授本章內(nèi)容圖的連通性刻畫(huà)2第2頁(yè)，本講稿共29頁(yè)本次課主要內(nèi)容(一)、割邊及其性質(zhì)(二)、割點(diǎn)及其性質(zhì)(三)、塊及其性質(zhì)割邊、割點(diǎn)和塊3第3頁(yè)，本講稿共29頁(yè)研究圖的連通性的意義研究圖的連通性，主要研究圖的連通程度的刻畫(huà)，其意義是：圖論意義：圖的連通程度的高低，是圖結(jié)構(gòu)性質(zhì)的重要表征，圖的許多性質(zhì)都與其相關(guān)，例如：連通圖中任意兩點(diǎn)間不相交路的條數(shù)就與圖的連通程度有關(guān)。實(shí)際意義：圖的連通程度的高低，在與之對(duì)應(yīng)的通信網(wǎng)絡(luò)中，對(duì)應(yīng)于網(wǎng)絡(luò)“可靠性程度”的高低。網(wǎng)絡(luò)可靠性，是指網(wǎng)絡(luò)運(yùn)作的好壞程度，即指如計(jì)算機(jī)網(wǎng)絡(luò)、通信網(wǎng)絡(luò)等對(duì)某個(gè)組成部分崩潰的容忍程度。網(wǎng)絡(luò)可靠性，是用可靠性參數(shù)來(lái)描述的。參數(shù)主要分確定性參數(shù)與概率性參數(shù)。4第4頁(yè)，本講稿共29頁(yè)確定性參數(shù)主要考慮網(wǎng)絡(luò)在最壞情況下的可靠性度量，常稱(chēng)為網(wǎng)絡(luò)拓?fù)涞摹叭蒎e(cuò)性度量”，通常用圖論概念給出，其中，本章將介紹的圖的連通度就是網(wǎng)路確定性參數(shù)之一。近年來(lái)，人們又提出了“堅(jiān)韌度”、“核度”、“整度”等描述網(wǎng)絡(luò)容錯(cuò)性的參數(shù)。概率性參數(shù)主要考慮網(wǎng)絡(luò)中處理器與信關(guān)以隨機(jī)的、彼此獨(dú)立的按某種確定性概率損壞的情況下，網(wǎng)絡(luò)的可靠性度量，常稱(chēng)為網(wǎng)絡(luò)拓?fù)涞摹翱煽啃远攘俊薄?一)、割邊及其性質(zhì)定義1邊e為圖G的一條割邊，如果。紅色邊為該圖的割邊5第5頁(yè)，本講稿共29頁(yè)注：割邊又稱(chēng)為圖的“橋”。圖的割邊有如下性質(zhì)：定理1邊e是圖G的割邊當(dāng)且僅當(dāng)e不在G的任何圈中。證明：可以假設(shè)G連通。若不然。設(shè)e在圖G的某圈C中，且令e=uv.考慮P=C-e,則P是一條uv路。下面證明G-e連通。對(duì)任意x,yV(G-e)由于G連通，所以存在x---y路Q(chēng).若Q不含e，則x與y在G-e里連通；若Q含有e，則可選擇路：x---uPv---y,說(shuō)明x與y在G-e里也連通。所以,若邊e在G的某圈中，則G-e連通。但這與e是G的割邊矛盾！“必要性”6第6頁(yè)，本講稿共29頁(yè)“充分性”如果e不是G的割邊，則G-e連通，于是在G-e中存在一條u---v路，顯然：該路并上邊e得到G中一個(gè)包含邊e的圈，矛盾。推論1e為連通圖G的一條邊，如果e含于G的某圈中，則G-e連通。證明：若不然，G-e不連通，于是e是割邊。由定理1，e不在G的任意圈中，矛盾！例1求證:(1)若G的每個(gè)頂點(diǎn)的度數(shù)均為偶數(shù)，則G沒(méi)有割邊;(2)若G為k正則二部圖(k≧2)，則G無(wú)割邊。證明:(1)若不然，設(shè)e=uv為G的割邊。則G-e的含有頂點(diǎn)u的那個(gè)分支中點(diǎn)u的度數(shù)為奇，而其余點(diǎn)的度數(shù)為偶數(shù)，與握手定理推論相矛盾！7第7頁(yè)，本講稿共29頁(yè)

(2)若不然，設(shè)e=uv為G的割邊。取G-e的其中一個(gè)分支G1,顯然，G1中只有一個(gè)頂點(diǎn)的度數(shù)是k-1,其余點(diǎn)的度數(shù)為k。并且G1仍然為偶圖。

假若G1的兩個(gè)頂點(diǎn)子集包含的頂點(diǎn)數(shù)分別為m與n，并且包含m個(gè)頂點(diǎn)的頂點(diǎn)子集包含度為k-1的那個(gè)點(diǎn)，那么有：km-1=kn。但是因k≧2，所以等式不能成立！注：該題可以直接證明G中任何一條邊均在某一圈中，由定理1得出結(jié)論。邊割集簡(jiǎn)介邊割集跟回路、樹(shù)等概念一樣，是圖論中重要概念。在應(yīng)用上，它是電路網(wǎng)絡(luò)圖論的基本概念之一。所以，下面作簡(jiǎn)單介紹。8第8頁(yè)，本講稿共29頁(yè)

定義2一個(gè)具有n個(gè)頂點(diǎn)的連通圖G,定義n-1為該連通圖的秩；具有p個(gè)分支的圖的秩定義為n-p。記為R(G)。

(1)R(G-S)=n-2;

定義3設(shè)S是連通圖G的一個(gè)邊子集，如果：

(2)對(duì)S的任一真子集S1,有R(G-S1)=n-1。稱(chēng)S為G的一個(gè)邊割集，簡(jiǎn)稱(chēng)G的一個(gè)邊割。例2邊子集：S1=｛a,c,e｝,S2=｛a,b,｝,S3=｛f｝是否是下圖G的邊割？agedcbhfi圖G9第9頁(yè)，本講稿共29頁(yè)

解:S1不是；S2與S3是。

定義4在G中，與頂點(diǎn)v關(guān)聯(lián)的邊的集合，稱(chēng)為v的關(guān)聯(lián)集，記為：S(v)。agedcbhfi圖G

例3關(guān)聯(lián)集是割集嗎？為什么？

答：不一定！如在下圖中，關(guān)聯(lián)集｛a,b｝是割集，但是，關(guān)聯(lián)集｛d,e,f｝不是割集。10第10頁(yè)，本講稿共29頁(yè)

定義5在G中，如果V=V1∪V2,V1∩V2=Φ,E1是G中端點(diǎn)分屬于V1與V2的G的邊子集，稱(chēng)E1是G的一個(gè)斷集。agedcbhfi圖G

在上圖G中：｛d,e｝,｛f｝,｛e,d,f｝等都是G的斷集。一個(gè)圖若按斷集S來(lái)畫(huà)，形式為：S11第11頁(yè)，本講稿共29頁(yè)

注：割集、關(guān)聯(lián)集是斷集，但逆不一定。斷集和關(guān)聯(lián)集之間的關(guān)系為：

定理2任意一個(gè)斷集均是若干關(guān)聯(lián)集的環(huán)和。

定理3連通圖G的斷集的集合作成子圖空間的一個(gè)子空間，其維數(shù)為n-1。該空間稱(chēng)為圖的斷集空間。(其基為n-1個(gè)線(xiàn)性無(wú)關(guān)的關(guān)聯(lián)集)

例4求出下圖G的所有斷集。edcbaf123412第12頁(yè)，本講稿共29頁(yè)

解：容易知道：S(1),S(2),S(3)是線(xiàn)性無(wú)關(guān)斷集。cba1234S(1)daf123S(2)ecf1234S(3)dcbf1234ebaf123413第13頁(yè)，本講稿共29頁(yè)edca1234edb1234

上圖形成的斷集空間為：

定義6設(shè)G是連通圖，T是G的一棵生成樹(shù)。如果G的一個(gè)割集S恰好包含T的一條樹(shù)枝，稱(chēng)S是G的對(duì)于T的一個(gè)基本割集。14第14頁(yè)，本講稿共29頁(yè)

例如：在圖G中fedcba圖G

G的相對(duì)于T的基本割集為：｛a,e｝,｛f,c｝,｛f,b,e｝,｛d｝.

關(guān)于基本割集，有如下重要結(jié)論：

定理4連通圖G的斷集均可表為G的對(duì)應(yīng)于某生成樹(shù)T的基本割集的環(huán)和。15第15頁(yè)，本講稿共29頁(yè)

定理5連通圖G對(duì)應(yīng)于某生成樹(shù)T的基本割集的個(gè)數(shù)為n-1,它們作成斷集空間的一組基。

注：到目前為止，我們?cè)谧訄D空間基礎(chǔ)上，先后引進(jìn)了圖的回路空間和斷集空間，它們都是子圖空間的子空間，這些概念，均是網(wǎng)路圖論的基本概念，當(dāng)然也是代數(shù)圖論的基本概念。(二)、割點(diǎn)及其性質(zhì)

定義7在G中，如果E(G)可以劃分為兩個(gè)非空子集E1與E2,使G[E1]和G[E2]以點(diǎn)v為公共頂點(diǎn)，稱(chēng)v為G的一個(gè)割點(diǎn)。16第16頁(yè)，本講稿共29頁(yè)

在圖G1中，點(diǎn)v1,v2均是割點(diǎn)；在G2中，v5是割點(diǎn)。v1v2v3v4e3e1e2e4e5e6圖G1v1v3v2v4v5圖G2

定理6G無(wú)環(huán)且非平凡，則v是G的割點(diǎn)，當(dāng)且僅當(dāng)

證明：“必要性”

設(shè)v是G的割點(diǎn)。則E(G)可劃分為兩個(gè)非空邊子集E1與E2,使G[E1],G[E2]恰好以v為公共點(diǎn)。由于G沒(méi)有環(huán)，所17第17頁(yè)，本講稿共29頁(yè)以，G[E1],G[E2]分別至少包含異于v的G的點(diǎn)，這樣，G-v的分支數(shù)比G的分支數(shù)至少多1，所以：“充分性”由割點(diǎn)定義結(jié)論顯然。定理7v是樹(shù)T的頂點(diǎn)，則v是割點(diǎn)，當(dāng)且僅當(dāng)v是樹(shù)的分支點(diǎn)。證明：“必要性”若不然，有deg(v)=1,即v是樹(shù)葉，顯然不能是割點(diǎn)?！俺浞中浴痹O(shè)v是分支點(diǎn)，則deg(v)>1.于是設(shè)x與y是v的鄰點(diǎn)，由樹(shù)的性質(zhì)，只有唯一路連接x與y，所以G-v分離x與y.即v為割點(diǎn)。18第18頁(yè)，本講稿共29頁(yè)定理8設(shè)v是無(wú)環(huán)連通圖G的一個(gè)頂點(diǎn)，則v是G的割點(diǎn)，當(dāng)且僅當(dāng)V(G-v)可以劃分為兩個(gè)非空子集V1與V2,使得對(duì)任意x∈V1,y∈V2,點(diǎn)v在每一條xy路上。證明：“必要性”

v是無(wú)環(huán)連通圖G的割點(diǎn)，由定理6，G-v至少有兩個(gè)連通分支。設(shè)其中一個(gè)連通分支頂點(diǎn)集合為V1,另外連通分支頂點(diǎn)集合為V2,即V1與V2構(gòu)成V的劃分?！俺浞中浴睂?duì)于任意的x∈V1,y∈V2，如果點(diǎn)v不在某一條xy路上，那么，該路也是連接G-v中的x與y的路，這與x,y處于G-v的不同分支矛盾。若v不是圖G的割點(diǎn)，那么G-v連通，因此在G-v中存在x,y路，當(dāng)然也是G中一條沒(méi)有經(jīng)過(guò)點(diǎn)v的x,y路。矛盾。19第19頁(yè)，本講稿共29頁(yè)例5求證：無(wú)環(huán)非平凡連通圖至少有兩個(gè)非割點(diǎn)。證明：由于G是無(wú)環(huán)非平凡連通圖，所以存在非平凡生成樹(shù)，而非平凡生成樹(shù)至少兩片樹(shù)葉，它不能為割點(diǎn)，所以，它也不能為G的割點(diǎn)。證明：設(shè)T是G的一棵生成樹(shù)。由于G有n-2個(gè)割點(diǎn)，所以，T有n-2個(gè)割點(diǎn)，即T只有兩片樹(shù)葉，所以T是一條路。這說(shuō)明，G的任意生成樹(shù)為路。例6求證：恰有兩個(gè)非割點(diǎn)的連通單圖是一條路。一個(gè)單圖的任意生成樹(shù)為路，則該圖為圈或路，若為圈，則G沒(méi)有割點(diǎn)，矛盾，所以，G為路。例7求證：若v是單圖G的割點(diǎn)，則它不是G的補(bǔ)圖的割點(diǎn)。20第20頁(yè)，本講稿共29頁(yè)證明：v是單圖G的割點(diǎn)，則G-v至少兩個(gè)連通分支?，F(xiàn)任取,如果x,y在G-v的同一分支中，令u是與x,y處于不同分支的點(diǎn)，那么，通過(guò)u，可說(shuō)明，x與y在G-v的補(bǔ)圖中連通。若x,y在G-v的不同分支中，則它們?cè)贕-v的補(bǔ)圖中鄰接。所以，若v是G的割點(diǎn)，則v不是其補(bǔ)圖的割點(diǎn)。(三)、塊及其性質(zhì)

定義8沒(méi)有割點(diǎn)的連通圖稱(chēng)為是一個(gè)塊圖，簡(jiǎn)稱(chēng)塊；G的一個(gè)子圖B稱(chēng)為是G的一個(gè)塊，如果(1),它本身是塊；(2),若沒(méi)有真包含B的G的塊存在。例7找出下圖G中的所有塊。21第21頁(yè)，本講稿共29頁(yè)解：由塊的定義得：圖G22第22頁(yè)，本講稿共29頁(yè)定理9若|V(G)|≧3,則G是塊，當(dāng)且僅當(dāng)G無(wú)環(huán)且任意兩頂點(diǎn)位于同一圈上。證明：(必要性）設(shè)G是塊。因G沒(méi)有割點(diǎn)，所以，它不能有環(huán)。對(duì)任意u,v∈V(G),下面證明u,v位于某一圈上。對(duì)d(u,v)作數(shù)學(xué)歸納法證明。當(dāng)d(u,v)=1時(shí)，由于G是至少3個(gè)點(diǎn)的塊，所以，邊uv不能為割邊，否則，u或v為割點(diǎn)，矛盾。由割邊性質(zhì)，uv必然在某圈中。設(shè)當(dāng)d(u,v)<k時(shí)結(jié)論成立。設(shè)當(dāng)d(u,v)=k。設(shè)P是一條最短(u,v)路，w是v前面一點(diǎn)，則d(u,v)=k-123第23頁(yè)，本講稿共29頁(yè)由歸納假設(shè)，u與w在同一圈C=P1∪P2上。uwvPP2P1考慮G-w.由于G是塊，所以G-w連通。設(shè)Q是一條在G-w中的(u,v)路，并且設(shè)它與C的最后一個(gè)交點(diǎn)為x。uwvQP2P1x24第24頁(yè)，本講稿共29頁(yè)則uP1xvwP2為包含u,v的圈。

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

(充分性)如果v屬于G的兩個(gè)不同塊，我們證明：v一定是圖G的割點(diǎn)。25第25頁(yè)，本講稿共29頁(yè)如果包含v的其中一個(gè)塊是環(huán)，顯然v是割點(diǎn)；