圖論課件第3章

yzwang@第三章圖的連通度割邊、割點和塊連通度應(yīng)用圖的寬距離和寬直徑G3G4刪去任意一條邊后仍連通，但刪去點u后便不連通考察G3和G4刪去任意一條邊或任意一個點后仍連通，但從直觀上看G4的連通程度比G3高。刪去任意一條邊后便不連通G1uG2圖的連通性，主要用來刻畫圖的連通程度，其意義是

理論意義：圖的連通程度的高低，是圖結(jié)構(gòu)性質(zhì)的重要表征，圖的許多性質(zhì)都與其相關(guān)，例如：連通圖中任意兩點間不相交路的條數(shù)就與圖的連通程度有關(guān)。

實際意義：圖的連通程度的高低，對應(yīng)于通信網(wǎng)絡(luò)“可靠性程度”的高低。網(wǎng)絡(luò)可靠性，是指網(wǎng)絡(luò)運作的好壞程度，即指如計算機網(wǎng)絡(luò)、通信網(wǎng)絡(luò)等對某個組成部分崩潰的容忍程度。網(wǎng)絡(luò)可靠性，是用可靠性參數(shù)來描述的，主要分為“確定性參數(shù)”與“概率性參數(shù)”。研究圖的連通性的意義確定性參數(shù)主要考慮網(wǎng)絡(luò)在最壞情況下的可靠性度量，常稱為網(wǎng)絡(luò)拓撲的“容錯性度量”，通常用圖論概念給出，其中，本章將介紹的圖的連通度就是網(wǎng)絡(luò)確定性參數(shù)之一。近年來，人們又提出了“堅韌度”、“核度”、“整度”等描述網(wǎng)絡(luò)容錯性的參數(shù)。概率性參數(shù)主要考慮網(wǎng)絡(luò)中處理器與信關(guān)以隨機的、彼此獨立的按某種確定性概率損壞的情況下，網(wǎng)絡(luò)的可靠性度量，常稱為網(wǎng)絡(luò)拓撲的“可靠性度量”。3.1割邊、割點和塊定義

設(shè)e是圖G的一條邊，若ω(G-e)＞ω(G)，則稱e為G的割邊。

例(1)

若G連通，則割邊是指刪去后使G不連通的邊，故非平凡樹的每條邊均為割邊。(2)

下圖中，邊e1和e2為割邊，而其余邊均不為割邊。e1e2一、割邊及其性質(zhì)定理

e是圖G的割邊當且僅當e不在G的任何圈中。證明因結(jié)論若在G的含e的連通分支中成立，則必在G中成立，所以我們不妨假定G連通。若Γ含e，用P替換e后也可得到G-e中一條(x,y)路，以上表明G-e連通，這與e是割邊矛盾，所以e不在G的任何圈中。必要性設(shè)e=uv是圖G的割邊，若e含在圈C中，令P=C-e。易知P是G-e中一條(u,v)路。任取G-e中兩個不同點x和y，因G連通，故G中存在(x,y)路Γ。若Γ不含e，則Γ也是G-e中一條(x,y)路；充分性設(shè)e=uv，若e不是G的割邊，則G-e仍連通，從而在G-e中存在(u,v)路P，這樣P+e便是G中含e的圈，這與假設(shè)“e不在G的任何圈中”矛盾。所以e是G的割邊。注：以上定理表明圈中的邊一定不是割邊，所以刪去圈中的邊不會破壞圖的連通性。推論

設(shè)e是連通圖G的任意一條邊，若e含在G的某圈中，則G-e仍連通。例

求證：(1)若G的每個頂點的度數(shù)均為偶數(shù)，則G沒有割邊;(2)若G為k正則二部圖(k≥2)，則G無割邊。證明

(1)若不然，設(shè)e=uv為G的割邊。則G-e的含有頂點u(或v)的那個分支中點u(或v)的度數(shù)必為奇數(shù)，而其余點的度數(shù)為偶數(shù)，與“度數(shù)為奇數(shù)的頂點的個數(shù)為偶數(shù)”相矛盾。(2)若不然，設(shè)e=uv為G的割邊。假設(shè)G1為G-e的包含頂點u的連通分支，顯然G1中除了點u的度數(shù)為k-1外，其余點的度數(shù)均為k。不妨假設(shè)S包含頂點u，則ks-1=kt。顯然G1仍為偶圖，設(shè)其二部劃分為S和T且|S|=s，|T|=t。但是因k≥2，所以等式不能成立！因此e一定不是割邊。二、割點及其性質(zhì)定義

圖G=(V,E)的頂點v稱為割點，如果E可劃分為兩個非空子集E1和E2，使得G[E1]和G[E2]恰有一個公共頂點v。例

圖中點u1,u2,u3和u4是割點，其余點均不為割點。u1u2u3u4注：(1)若ω(G-v)>ω(G)，則v必為G的割點。

(2)

若G無環(huán)，則v是G的割點當且僅當

ω(G-v)>ω(G)。

(3)

若無環(huán)圖G連通，則割點是指刪去該點使G不連通的點。定理

設(shè)v是樹G的頂點，則v是G的割點當且僅當d(v)>1。證明

必要性若不然，有d(v)=1，即v是樹葉，顯然不可能是割點。充分性設(shè)頂點v的度數(shù)大于1。設(shè)x和y是與v相鄰的兩點，由樹的性質(zhì)知，只有唯一的路連接x與y，所以G-v分離x與y。因此，v是割點。定理

設(shè)v是無環(huán)連通圖G的一個頂點，則v是G的割點當且僅當V(G–v)可劃分為兩個非空頂點子集V1與V2，使得對任意的x∈V1，y∈V2，點v都在每一條(x,y)路上。證明

充分性若v不是圖G的割點，那么G-v連通，因此在G-v中存在(x,y)路，當然也是G中一條沒有經(jīng)過點v的(x,y)路。與已知條件矛盾。必要性設(shè)v是無環(huán)連通圖G的割點，則G-v至少有兩個連通分支。設(shè)V1是其中一個連通分支的頂點集，V2為其余頂點構(gòu)成的集合。對于任意的x∈V1，y∈V2，如果點v不在某一條(x,y)路上，那么該路也是G-v中連接x與y的一條路，這與x,y處于G-v的不同連通分支矛盾。例

求證：無環(huán)非平凡連通圖至少有兩個點不是割點。證明由于G是無環(huán)非平凡連通圖，所以存在非平凡生成樹。非平凡生成樹至少兩片樹葉，它們不能為生成樹的割點。顯然，它們也不能為G的割點。證明設(shè)T是連通簡單圖G的一棵生成樹。例求證：恰有兩個非割點的連通簡單圖是一條路。一個簡單圖的任意生成樹為路，則該圖為圈或路。由于G有n-2個割點，所以，T有n-2個割點，因此T只有兩片樹葉，所以T是一條路。這說明，G的任意生成樹為路。若為圈，則G沒有割點，矛盾！所以G為路。例

求證：若v是簡單圖G的割點，則v不是G的補圖的割點。證明容易驗證，因為v是G的割點，所以G-v一定不是連通圖。從而G–v的補圖是連通圖。因此，在G的補圖中刪去頂點v不會增加圖的連通分支數(shù)。所以，v不是G的補圖的割點。三、塊及其性質(zhì)定義

沒有割點的連通圖稱為塊圖，簡稱塊。若圖G的子圖B是塊，且G中沒有真包含B的子圖也是塊，則稱B是G的塊。注：

(1)若e是圖G的割邊或e是一個環(huán)，則G[{e}]是G的塊；

(2)僅有一個點的塊，要么是孤立點，要不是環(huán)；

(3)至少有兩個點的塊無環(huán)；

(4)至少有三個點的塊無割邊。例

圖G如圖(a)所示，G的所有塊如圖(b)所示。(a)(b)定理

設(shè)圖G的階至少為3，則G是塊當且僅當G無環(huán)并且任意兩點都位于同一個圈上。證明充分性此時G顯然連通。若G不是塊，則G中有割點v。由于G無環(huán)，所以G-v至少有兩個連通分支。設(shè)x,y是G-v的兩個不同分支中的點，則x,y在G中不能位于同一圈上，矛盾！必要性

G顯然無環(huán)，否則G中存在割點。下證G中任意兩點u和v位于同一圈上，對距離d(u,v)作歸納。當d(u,v)=1時，由于G是至少有3個點的塊，所以，邊uv不能為割邊。由割邊性質(zhì)知，uv必然在某圈中。設(shè)結(jié)論對距離小于k的任意兩點成立。假定u,v為距離等于k的任意兩點。設(shè)P是一條最短(u,v)路，w是v前面一點，則d(u,w)=k-1。由歸納假設(shè)知，u與w在同一圈C上。

xuwvCP2P1

Q

若v也在C中，則已得到證明。下設(shè)v不在C中。因G是塊，無割點，故G-w仍連通，于是存在一條(u,v)路Q。設(shè)點x是Q與C的最后一個公共點。于是P1,Q的x到v段，邊vw以及P2的w到u段共同構(gòu)成一個圈C*，且u與v均在C*上。點x將C劃分為兩條(u,x)路P1和P2，不妨設(shè)w在P2上。推論

設(shè)G的階至少為3，則G是塊當且僅當G無孤立點且任意兩條邊都在同一個圈上。證明設(shè)G無孤立點且任意兩條邊都在同一個圈上。此時G無環(huán)，因為環(huán)和任何一條邊都不可能在一個圈上。此時，必然任意兩個點也在同一個圈上，因此G是塊。反之，設(shè)G是塊。顯然G無孤立點。任取G中兩條邊e1和e2。在邊e1和e2上各插入一個新的頂點v1和v2，使e1和e2均成為兩條邊，記這樣得到的圖為G*。由于G是至少有三個點的塊，從而G無割邊，因此v1和v2必然不是G*的割點，所以G*是階大于4的塊。因此v1和v2在G*的同一個圈上，于是e1和e2在G中位于同一個圈上。定理

點v是圖G的割點當且僅當v至少屬于G的兩個不同的塊。證明

必要性設(shè)v是G的割點。由割點定義知E(G)可以劃分為兩個邊子集E1與E2使得G[E1]與G[E2]有唯一公共頂點v。設(shè)B1與B2分別是G[E1]和G[E2]中包含v的塊，顯然它們也是G的塊。因此v至少屬于G的兩個不同塊。充分性

設(shè)點v屬于G的兩個不同塊B1和B2。如果B1和B2其中一個是環(huán)，顯然v是割點。現(xiàn)在假設(shè)B1與B2都不是環(huán)。顯然，B1∪B2∪P無割點。這與B1與B2是塊矛盾！那么B1與B2分別至少有兩個頂點。假如v不是割點，在B1與B2中分別找異于v的一個點x與y，則在G-v中有連接x與y的路P。注：兩個不同塊的公共頂點只能是割點，即塊與塊只能由割點相聯(lián)結(jié)，因此可以通過割點搜尋塊。定義設(shè)G是非平凡連通圖，B1,B2,…,Bk是G的全部塊，而v1,v2,…,vt是G的全部割點。構(gòu)作G的塊割點樹bc(G)：它的頂點是G的塊和割點，uv是bc(G)的一條邊當且僅當u與v中有一個是G的割點，另一個是該割點聯(lián)結(jié)的塊。例注：(1)bc(G)是一個沒有圈的連通圖，即為樹。

(2)若G本身就是一個塊，則bc(G)是平凡圖。

(3)若G本身不是塊，則bc(G)至少有三個點并且葉子點為G的只含一個割點的塊。B1B5B6B3B2B4125634GB1B2B3B7B4B5B6125634bc(G)B73.2連通度一、連通度和邊連通度定義給定連通圖G，設(shè)V’是V(G)的頂點子集，若G-V’

不連通，則稱V’為G的頂點割，含有k個頂點的頂點割稱為G的k頂點割。G中點數(shù)最少的頂點割稱為最小點割。

例G2V1={u}，V2={u,v}均為G1的頂點割，其中V1為1點割，V2為2點割，G2沒有頂點割。G1uvw注：(1)若G是非平凡連通圖，則v是G的割點當且僅當{v}是

G的1頂點割。

(2)完全圖沒有頂點割，實際上也只有以完全圖為生成子圖的圖沒有頂點割。定義

對n階連通圖G，若G存在頂點割，則稱G的最小頂點割中的點數(shù)為G的連通度；否則稱n-1為其連通度。G的連通度符號表示為κ(G)，簡記為κ；非連通圖或平凡圖的連通度定義為0。連通度也可描述為“使圖不連通或成為平凡圖，至少需要刪去的點數(shù)”。例

(1)κ(Kn)=n-1；(2)κ(Cn)=2，其中Cn為n圈，n≥3。例求下列各圖的連通度。G1G2G3G4解

κ(G1)=1，κ(G2)=3，κ(G3)=1，κ(G4)=2。定義若一個圖的連通度至少為k，則稱該圖是k連通的。注：(1)非平凡連通圖均是1連通的。

(2)圖G是2連通的當且僅當G連通、無割點且至少含有3個點。

(3)K2連通、無割點，但連通度為1。定義

設(shè)G為連通圖，稱使G-E’不連通的G的邊子集E’為G的邊割，含有k條邊的邊割稱為k邊割。邊數(shù)最少的邊割稱為最小邊割。定義設(shè)G是非平凡連通圖，若M是G的最小邊割，則稱|M|為G的邊連通度。記為λ(G)，簡記為λ。對非連通圖或平凡圖G，定義λ(G)=0。例G1的每條邊均可構(gòu)成1邊割；{e1,e2}為G3的2邊割。G1G2G4G3e1e2λ(G1)=1，λ(G2)=3，λ(G3)=2，λ(G4)=3注：對連通圖G，由定義易知，e是G的割邊當且僅當{e}是G的1邊割。定義若一個圖的邊連通度至少為k，稱該圖是k邊連通的。注：(1)非平凡連通圖均是1邊連通的;

(2)圖G是2邊連通的當且僅當G連通、無割邊且至少含有兩個點。例G1v5v4v3v2v1v6G2v4v3v2v1G1是1連通的，1邊連通的，但不是2連通的，2邊連通的。G2是3連通的，3邊連通的，但不是4連通的，4邊連通的。二、連通度的性質(zhì)定理

對任意的圖G，有

κ(G)≤λ(G)≤δ(G)。

證明若G為平凡圖或不連通，則κ(G)=λ(G)=0，結(jié)論顯然成立。下設(shè)G為非平凡連通圖。對任意的u∈V(G)，由于全體與u相關(guān)聯(lián)的邊構(gòu)成的集合是G的一個邊割集，從而推知λ(G)≤δ(G)成立。下面對λ(G)用歸納法證明κ(G)≤λ(G)。當λ(G)=1時，κ(G)=λ(G)=1。設(shè)對所有滿足λ(G)<k（k≥2）的圖G，κ(G)≤λ(G)成立。

設(shè)E’是G的一個k邊割，取e∈E’。假設(shè)G為邊連通度等于k的任意一個圖。令H=G-e，則λ(H)=k-1。由歸納假設(shè)知，κ(H)≤k-1。情況1

H含有完全圖作為生成子圖，則G也如此。此時

κ(G)=|V(G)|-1=|V(H)|-1=κ(H)≤k-1。情況2

H的任意生成子圖均不為完全圖。

設(shè)S是H的一個κ(H)頂點割，于是|S|≤k-1。若G-S不連通，則κ(G)≤|S|≤k-1。若G-S連通，因H-S不連通，故e是G-S的割邊。此時，若G-S恰含兩個點，則|V(G)|=|S|+2。于是

κ(G)≤|V(G)|-1=|S|+1≤k。若G-S至少含3個點，則G-S包含割點v，于是S∪{v}是G的頂點割，從而

κ(G)≤|S∪{v}|≤k。所以總有

κ(G)≤k=λ(G)。

例

滿足κ(G)<λ(G)<δ(G)的圖κ=1λ=2δ=3

定理

設(shè)G是具有m條邊的n階連通圖，則證明由握手定理得引理

設(shè)G是n階簡單圖，若δ(G)≥，則G必連通。證明若G不連通，則G至少有兩個連通分支，從而必有一個分支H滿足|V(H)|≤。因G是簡單圖，從而這與已知矛盾，所以G必連通。

定理

設(shè)G是n階簡單圖，對正整數(shù)k<n，若則G是k連通的。于是證明任意刪去G中k-1個點，記所得之圖為H，則因δ(H)是整數(shù)，故而n-k+1是H的點數(shù)，由引理知H是連通的。所以G是k連通的。定理設(shè)G是n階簡單圖，若δ(G)≥，則λ(G)=δ(G)。證明顯然G是連通的。若λ(G)≠δ(G)，則λ(G)<δ(G)。此時G中存在邊割M，滿足|M|=λ(G)<δ(G)，同時G-M是由兩個不相交的子圖G1和G2所構(gòu)成。設(shè)M中的邊和G1的p個點相關(guān)聯(lián)，顯然p≤λ(G)。由握手定理可得由于δ(G)>λ(G)，故上式表明|V(G1)|>p。因此G1中存在只與G1中的點相鄰的點，設(shè)此點為x，于是所以|V(G1)|≥δ(G)+1。同理，|V(G2)|≥δ(G)+1。于是，n=|V(G1)|+|V(G2)|≥2δ(G)+2。從而與已知條件矛盾，所以λ(G)=δ(G)。三、Menger定理Menger定理是圖的連通性問題的核心定理之一，它揭示了圖的連通度與不同頂點對間的不相交路的數(shù)目之間的關(guān)系。定義圖中兩條(x,y)路稱為內(nèi)部不相交的或獨立的，如果此兩條路僅x和y是其公共點。定義設(shè)x與y是圖G中兩個不同點，稱一組點(邊)分離x與y，是指G中刪去這組點(邊)后不再有(x,y)路。例點集{u1,u3}分離點a與b。邊集{u1b,u2u3,au5}分離點a與b。u5abu4u2u1u3定理

(1)

設(shè)x和y是圖G中的兩個不相鄰點，則G中分離x和y的最少點數(shù)等于獨立的(x,y)路的最大數(shù)目。

(2)設(shè)x和y是圖G中的兩個不同點，則G中分離x和y的最少邊數(shù)等于邊不重的(x,y)路的最大數(shù)目。

例在該圖中，獨立的(u,v)路的最大條數(shù)是2，分離點u與v的最小點集是{u1,u2}，包含兩個頂點。在該圖中，邊不重的(u,v)路的最大條數(shù)是2，分離點u與v的最小邊集是{u1v,u2u3}，包含兩條邊。uu4vu3u2u1定理

(1)一個非平凡圖G是k(k≥2)連通的當且僅當G的任意兩個不同頂點間至少存在k條獨立的路；(2)一個非平凡圖G是k(k≥2)邊連通的當且僅當G的任意兩個不同頂點間至少存在k條邊不重的路。例設(shè)G是k連通圖，S是由G中任意k個頂點構(gòu)成的集合。若圖H是由G通過添加一個新點w以及連接w到S中所有頂點得到的新圖，求證：H是k連通的。證明首先，分離屬于G的兩個不相鄰頂點至少需要k個點。注：上述定理是Whitney在1932年借助Menger定理給出的。這也是人們熟知的所謂的“Menger定理”。注：由“任意兩個不相鄰的頂點之間存在k條獨立的路”必能推出“任意兩個相鄰的頂點之間也存在k條獨立的路”。其次，分離w與G的不屬于S的頂點至少需要k個點。因此，分離H中任意兩個不相鄰的頂點至少需要k個點，從而，H中任意兩個不相鄰的頂點間至少存在k條獨立的路。所以，H中任意兩個不同頂點間至少存在k條獨立的路，因此H是k連通的。推論

設(shè)G是階至少為3的圖，則以下三個命題等價。(1)G是2連通的無環(huán)圖；(2)G無環(huán)且任意兩點都位于同一個圈上；(3)G無孤立點且任意兩條邊都在同一個圈上。證明

(1)=>(2)

因為G是2連通的，則G的任意兩個頂點間存在兩條獨立的路P1與P2，顯然這兩條路構(gòu)成包含這兩個頂點的圈。(2)=>(3)

G中顯然沒有孤立點。設(shè)e1與e2是G的任意兩條邊，在e1與e2上分別添加兩點u與v得圖H，則H是2連通的，因此H的任意兩個頂點在同一個圈上，即u與v在同一個圈上，也即e1與e2在同一個圈上。(3)=>(1)顯然G無環(huán)。設(shè)u與v是圖G的任意兩個不相鄰頂點，由于G無孤立點，所以可設(shè)e1,e2分別與u,v相關(guān)聯(lián)。因為e1,e2在同一個圈上，所以u與v在同一個圈上，因此分離u與v至少要去掉兩個頂點，即G是2連通的。3.3

應(yīng)用一個通訊網(wǎng)絡(luò)可以模型化為一個圖，圖中的點代表通訊站，邊代表通訊線。這樣，圖的點（邊）連通度對應(yīng)了網(wǎng)絡(luò)中容許失靈的通訊站（線）數(shù)目的一個界限。即圖的連通度對應(yīng)系統(tǒng)的可靠性。問題：如何構(gòu)造出在給定可靠性的條件下使成本盡量低的系統(tǒng)?圖論模型：對一個賦權(quán)圖G，試確定G的一個具有最小權(quán)的k連通生成子圖。注：(1)

對k=1，此問題即為求最小生成樹的問題；

(2)

對k>1，這是一個還未解決的困難問題。當G是完全圖，各邊的權(quán)均為1的特殊情況，問題是有解的。此時即求邊數(shù)最少的具有n個頂點的k連通圖G。由前面定理知，m條邊的n階k連通圖滿足所以若能構(gòu)造出邊數(shù)達到的n階k連通圖，則邊數(shù)將已達到最少。因此1962年，數(shù)學家Harary構(gòu)造了這類圖Hk,n，稱為Harary圖。Hk,n的構(gòu)造設(shè)V(Hk,n)={0,1,2…,n-1}。情況1.

k為偶，設(shè)k=2r。此時0與1,2,…,

r連線；1與2,3,…,

r+1連線；…；n-1與0,1,…,

r-1連線。如下圖中的H4,8所示。情況2.

k=2r+1，n為偶。先作H2r,n，再在i與(i+n/2)間添加邊i(i+n/2)（0≤i<n/2）。如下圖中的H5,8

所示。01765432

H4,8

01765432

H5,8

情況3.k=2r+1，n為奇。先作H2r,n，再在0和(n-1)/2，0和(n+1)/2，以及i和i+(n+1)/2(1≤i<(n-1)/2)間添加邊。如下圖中的H5,9所示。012345678H5,9可以證明：Hk,n是k連通的。3.4圖的寬距離和寬直徑一、問題背景分析評價互聯(lián)網(wǎng)絡(luò)的性能有多個指標，如網(wǎng)絡(luò)的開銷(通信與材料開銷)，網(wǎng)絡(luò)的容錯性(連通性)，網(wǎng)絡(luò)中信息傳遞的傳輸延遲等。所謂傳輸延遲，又稱為時間延遲，是指信息從信息源傳到目的地所需要的時間。如何度量網(wǎng)絡(luò)的傳輸延遲？信息從信息源到目的地需要經(jīng)過若干中間站存儲和轉(zhuǎn)發(fā)。因此，信息傳輸延遲可以用圖的頂點間距離來度量。當然，每條邊的長度可以定義為1。于是，網(wǎng)絡(luò)的最大通信延遲可以通過圖的直徑來度量。圖的直徑定義為：例

d(Pn)=n-1，d(Cn)=[n/2]，d(Kn)=1。在信息的單路徑傳輸中，分析通信延遲，只需要考慮網(wǎng)絡(luò)的直徑即可。但是，如果要一次傳輸?shù)男畔⒘枯^大，遠遠超出鏈路帶寬，就需要所謂的分包傳送。分包傳送，就是按照帶寬要求，把信息在起點進行分割打包，每個信息小包按照若干內(nèi)部不交路從起點傳到終點。上世紀90年代初，D.FrankHsu等圖論學者和一些計算機