圖論課件第3章

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

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

實(shí)際意義：圖的連通程度的高低，對(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ù)來描述的，主要分為“確定性參數(shù)”與“概率性參數(shù)”。研究圖的連通性的意義確定性參數(shù)主要考慮網(wǎng)絡(luò)在最壞情況下的可靠性度量，常稱為網(wǎng)絡(luò)拓?fù)涞摹叭蒎e(cuò)性度量”，通常用圖論概念給出，其中，本章將介紹的圖的連通度就是網(wǎng)絡(luò)確定性參數(shù)之一。近年來，人們又提出了“堅(jiān)韌度”、“核度”、“整度”等描述網(wǎng)絡(luò)容錯(cuò)性的參數(shù)。概率性參數(shù)主要考慮網(wǎng)絡(luò)中處理器與信關(guān)以隨機(jī)的、彼此獨(dú)立的按某種確定性概率損壞的情況下，網(wǎng)絡(luò)的可靠性度量，常稱為網(wǎng)絡(luò)拓?fù)涞摹翱煽啃远攘俊薄?.1割邊、割點(diǎn)和塊定義

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

例(1)

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

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

e是圖G的割邊當(dāng)且僅當(dāng)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中兩個(gè)不同點(diǎn)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的割邊。注：以上定理表明圈中的邊一定不是割邊，所以刪去圈中的邊不會(huì)破壞圖的連通性。推論

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

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

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

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

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

(2)

若G無環(huán)，則v是G的割點(diǎn)當(dāng)且僅當(dāng)

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

(3)

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

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

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

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

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

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

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

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

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

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

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

(4)至少有三個(gè)點(diǎn)的塊無割邊。例

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

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

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

xuwvCP2P1

Q

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

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

點(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è)不同塊。充分性

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

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

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

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

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

G的1頂點(diǎn)割。

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

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

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

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

(2)圖G是2連通的當(dāng)且僅當(dāng)G連通、無割點(diǎn)且至少含有3個(gè)點(diǎn)。

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

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

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

對(duì)任意的圖G，有

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

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

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

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

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

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

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

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

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

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

例

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

定理

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

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

定理

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

(1)

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

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

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

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

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

(1)=>(2)

因?yàn)镚是2連通的，則G的任意兩個(gè)頂點(diǎn)間存在兩條獨(dú)立的路P1與P2，顯然這兩條路構(gòu)成包含這兩個(gè)頂點(diǎn)的圈。(2)=>(3)

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

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

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

(2)

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

k為偶，設(shè)k=2r。此時(shí)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圖的寬距離和寬直徑一、問題背景分析評(píng)價(jià)互聯(lián)網(wǎng)絡(luò)的性能有多個(gè)指標(biāo)，如網(wǎng)絡(luò)的開銷(通信與材料開銷)，網(wǎng)絡(luò)的容錯(cuò)性(連通性)，網(wǎng)絡(luò)中信息傳遞的傳輸延遲等。所謂傳輸延遲，又稱為時(shí)間延遲，是指信息從信息源傳到目的地所需要的時(shí)間。如何度量網(wǎng)絡(luò)的傳輸延遲？信息從信息源到目的地需要經(jīng)過若干中間站存儲(chǔ)和轉(zhuǎn)發(fā)。因此，信息傳輸延遲可以用圖的頂點(diǎn)間距離來度量。當(dāng)然，每條邊的長度可以定義為1。于是，網(wǎng)絡(luò)的最大通信延遲可以通過圖的直徑來度量。圖的直徑定義為：例

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