圖論第三章圖的連通性

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

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

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

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

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

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

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

解:S1不是；S2與S3是。

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

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

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

定義5在G中，如果V=V1∪V2,V1∩V2=Φ,E1是G中端點分屬于V1與V2的G的邊子集，稱E1是G的一個斷集。agedcbhfi圖G

在上圖G中：｛d,e｝,｛f｝,｛e,d,f｝等都是G的斷集。一個圖若按斷集S來畫，形式為：S11第11頁，本講稿共29頁

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

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

定理3連通圖G的斷集的集合作成子圖空間的一個子空間，其維數(shù)為n-1。該空間稱為圖的斷集空間。(其基為n-1個線性無關的關聯(lián)集)

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

解：容易知道：S(1),S(2),S(3)是線性無關斷集。cba1234S(1)daf123S(2)ecf1234S(3)dcbf1234ebaf123413第13頁，本講稿共29頁edca1234edb1234

上圖形成的斷集空間為：

定義6設G是連通圖，T是G的一棵生成樹。如果G的一個割集S恰好包含T的一條樹枝，稱S是G的對于T的一個基本割集。14第14頁，本講稿共29頁

例如：在圖G中fedcba圖G

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

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

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

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

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

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

在圖G1中，點v1,v2均是割點；在G2中，v5是割點。v1v2v3v4e3e1e2e4e5e6圖G1v1v3v2v4v5圖G2

定理6G無環(huán)且非平凡，則v是G的割點，當且僅當

證明：“必要性”

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

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

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

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

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