應(yīng)用離散數(shù)學(xué)第六章第2講

第六章圖第2講圖的連通性通信網(wǎng)絡(luò)圖論應(yīng)用的一個(gè)重要方面就是通信網(wǎng)絡(luò)。如電話網(wǎng)絡(luò)、計(jì)算機(jī)網(wǎng)絡(luò)、管理信息系統(tǒng)、醫(yī)療數(shù)據(jù)網(wǎng)絡(luò)、銀行數(shù)據(jù)網(wǎng)絡(luò)、開關(guān)網(wǎng)絡(luò)等。這些網(wǎng)絡(luò)的基本要求是網(wǎng)絡(luò)中的各個(gè)用戶能夠快速安全地傳遞信息，不產(chǎn)生差錯(cuò)和故障，同時(shí)使建造和維護(hù)網(wǎng)絡(luò)所需費(fèi)用低。2024/1/27應(yīng)用離散數(shù)學(xué)第六章第2講2第六章第2講圖的連通性1.通路，回路2.連通性，點(diǎn)(邊)割集,點(diǎn)連通度

,邊連通度

3.Whitney定理,簡單連通圖,,之間的關(guān)系4.2-連通,2-邊連通的充要條件5.割點(diǎn),橋,塊的充要條件2024/1/27應(yīng)用離散數(shù)學(xué)第六章第2講3通路與回路通路，回路簡單通路，簡單回路初級(jí)通路，初級(jí)回路初級(jí)通路判定定理2024/1/27應(yīng)用離散數(shù)學(xué)第六章第2講4通路和回路通路，回路：給定圖G=<V,E>.設(shè)G中頂點(diǎn)和邊的交替序列為Γ=v0e1v1e2…elvl.若Γ滿足如下條件：vi-1是ei端點(diǎn)（G為有向圖時(shí)，要求vi-1是ei起始點(diǎn)，vi是ei的終點(diǎn)），則稱Γ為v0到vl的通路。v0和vl分別稱為此通路的起點(diǎn)和終點(diǎn)。Γ中所含邊的數(shù)目稱為Γ的長度。當(dāng)v0=vl時(shí)，稱通路為回路。2024/1/27應(yīng)用離散數(shù)學(xué)第六章第2講5afbcghied通路和回路簡單通路：若Γ中所有邊各異；簡單回路：類似；初級(jí)通路（路徑）：若Γ中所有頂點(diǎn)各異，所有邊也各異；初級(jí)回路（圈）：類似；奇圈，偶圈：圈的長度為奇數(shù)或偶數(shù)。復(fù)雜通路：Γ中有邊重復(fù)出現(xiàn)；復(fù)雜回路：類似2024/1/27應(yīng)用離散數(shù)學(xué)第六章第2講6通路和回路回路是通路的特殊情況；初級(jí)通路（回路）是簡單通路（回路），但反之不真；(頂點(diǎn)各異且邊各異則邊各異；反之不然)通路的表示法：頂點(diǎn)和邊的交替序列表示法；邊序列；在簡單圖中，可以用頂點(diǎn)序列2024/1/27應(yīng)用離散數(shù)學(xué)第六章第2講7通路和回路定理3：在一個(gè)n階圖中，若從頂點(diǎn)u到v（u和v不等）存在通路，則從u到v存在長度小于等于n-1的初級(jí)通路。證明：最多該通路中有n個(gè)頂點(diǎn)，如果n個(gè)頂點(diǎn)互不相同（初級(jí)通路），則最多為n-1條邊。2024/1/27應(yīng)用離散數(shù)學(xué)第六章第2講8通路和回路定理4：在一個(gè)n階圖中，如果存在v到自身的簡單回路，則從v到自身存在長度不超過n的初級(jí)回路。證明：類似。2024/1/27應(yīng)用離散數(shù)學(xué)第六章第2講9連通性無向圖的連通性：在無向圖G中，若頂點(diǎn)v1和v2之間存在通路，則稱v1與v2是連通的。規(guī)定v1與自身是連通的。連通圖：若無向圖G是平凡圖，或G中任意兩頂點(diǎn)都是連通的，則稱G是連通圖。否則稱G為非連通圖。2024/1/27應(yīng)用離散數(shù)學(xué)第六章第2講10平凡圖任意兩頂點(diǎn)都是連通的連通分支連通關(guān)系：設(shè)G=<V,E>為一無向圖，設(shè)R={<x,y>|x,y∈V且x與y連通}則R是自反的，對(duì)稱的，并且是傳遞的，因而R是V上的等價(jià)關(guān)系。連通分支：設(shè)R的不同等價(jià)類分別為V1，…，Vk,稱它們的導(dǎo)出子圖G[V1]，…，G[Vk]為G的連通分支，其連通分支的個(gè)數(shù)記為p(G)。若p(G)=1，則G是連通圖。2024/1/27應(yīng)用離散數(shù)學(xué)第六章第2講11圖中點(diǎn)之間的距離短程線：若兩點(diǎn)是連通的，則稱兩點(diǎn)之間的長度最短的通路為兩點(diǎn)之間的短程線。距離：短程線的長度稱為兩點(diǎn)之間的距離，記為d(v1,v2)。2024/1/27應(yīng)用離散數(shù)學(xué)第六章第2講12兩個(gè)連通分支如何定義連通度問題:如何定量比較無向圖連通性的強(qiáng)與弱?2024/1/27應(yīng)用離散數(shù)學(xué)第六章第2講13試想？？如何定義連通度點(diǎn)連通度:為了破壞連通性,至少需要?jiǎng)h除多少個(gè)頂點(diǎn)?邊連通度:為了破壞連通性,至少需要?jiǎng)h除多少條邊?說明:“破壞連通性”指p(G-V’)>p(G),或p(G-E’)>p(G),即“變得更加不連通”2024/1/27應(yīng)用離散數(shù)學(xué)第六章第2講14連通分支的個(gè)數(shù)割集(cutset)點(diǎn)割集(vertexcut)邊割集(edgecut)割點(diǎn)(cutvertex)割邊(cutedge)(橋)(bridge)2024/1/27應(yīng)用離散數(shù)學(xué)第六章第2講15點(diǎn)割集(vertexcutset)點(diǎn)割集:無向圖G=<V,E>,

V’V,滿足(1)p(G-V’)>p(G);(2)極小性:

V’’V’,p(G-V’’)=p(G),則稱V’為點(diǎn)割集.說明:“極小性”是為了保證點(diǎn)割集概念的非平凡性2024/1/27應(yīng)用離散數(shù)學(xué)第六章第2講16點(diǎn)割集(舉例)G1:{f},{a,e,c},{g,k,j},{b,e,f,k,h}G2:{f},{a,e,c},{g,k,j},{b,e,f,k,h}2024/1/27應(yīng)用離散數(shù)學(xué)第六章第2講17abcdfeghkjiabcefdjighkG1G2Question?割點(diǎn)(cut-point/cut-vertex)割點(diǎn):v是割點(diǎn)

{v}是割集例:G1中f是割點(diǎn),G2中無割點(diǎn)2024/1/27應(yīng)用離散數(shù)學(xué)第六章第2講18abcdfeghkjiabcefdjighkG1G2邊割集(edgecutset)邊割集:無向圖G=<V,E>,E’E,滿足(1)p(G-E’)>p(G);(2)極小性:

E’’E’,p(G-E’’)=p(G),則稱E’為邊割集.說明:“極小性”是為了保證邊割集概念的非平凡性2024/1/27應(yīng)用離散數(shù)學(xué)第六章第2講19邊割集(舉例)G1:{(a,f),(e,f),(d,f)},{(f,g),(f,k),(j,k),(j,i)}{(a,f),(e,f),(d,f),(f,g),(f,k),(f,j)},{(c,d)}G2:{(b,a),(b,e),(b,c)}2024/1/27應(yīng)用離散數(shù)學(xué)第六章第2講20abcdfeghkjiabcefdjighkG1G2注意：極小性割邊(cut-edge)(橋)割邊:(u,v)是割邊(橋)

{(u,v)}是邊割集例:G1中(f,g)是橋,G2中無橋2024/1/27應(yīng)用離散數(shù)學(xué)第六章第2講21abcdfelhkjiabcefdjighkG1G2g扇形割集(fancutset)IG(v)不一定是邊割集(不一定極小)IG(v)不是邊割集

v是割點(diǎn)扇形割集:E’是邊割集

E’

IG(v)例:{(a,g),(a,b)},{(g,a),(g,b),(g,c)},{(c,d)},{(d,e),(d,f)},{(a,b),(g,b),(g,c)}2024/1/27應(yīng)用離散數(shù)學(xué)第六章第2講22abcgdfe???關(guān)聯(lián)集:IG(v)={e|e與v關(guān)聯(lián)

}割點(diǎn)割點(diǎn)點(diǎn)連通度(vertex-connectivity)點(diǎn)連通度:G是無向連通非完全圖,(G)=min{|V’||V’是G的點(diǎn)割集}規(guī)定:(Kn)=n-1,G非連通:(G)=0例:(G)=1,(H)=2,(F)=3,(K5)=42024/1/27應(yīng)用離散數(shù)學(xué)第六章第2講23GHF邊連通度(edge-connectivity)邊連通度:G是無向連通圖,(G)=min{|E’||E’是G的邊割集}規(guī)定:G非連通:(G)=0例:(G)=1,(H)=2,(F)=3,(K5)=42024/1/27應(yīng)用離散數(shù)學(xué)第六章第2講24GHFk-連通圖,k-邊連通圖k-連通圖(k-connected):(G)kk-邊連通圖(k-edge-connected):(G)k例:彼得森圖=3,=3;它是1-連通圖,2-連通圖,3-連通圖,但不是4-連通圖;它是1-邊連通圖,2-邊連通圖,3-邊連通圖,但不是4-邊連通圖2024/1/27應(yīng)用離散數(shù)學(xué)第六章第2講25點(diǎn)連通度邊連通度Whitney定理定理10:

.證明:不妨設(shè)G是3階以上連通簡單非完全圖.()設(shè)d(v)=,則|IG(v)|=,IG(v)中一定有邊割集E’,所以|E’||IG(v)|=.(

)設(shè)E’是邊割集,|E’|=,從V(E’)中找出點(diǎn)割集V’,使得|V’|,所以|V’|.2024/1/27應(yīng)用離散數(shù)學(xué)第六章第2講26為圖的最小度。為點(diǎn)連通度為邊連通度Whitney定理(續(xù))證明(續(xù)):()設(shè)G-E’的2個(gè)連通分支是G1,G2.設(shè)uV(G1),vV(G2),使得(u,v)E(G).如下構(gòu)造V’’:eE’,選擇e的異于u,v的一個(gè)端點(diǎn)放入V’’.|V’’||E’|.G-V’’G-E’=G1G2,u和v在G-V’’中不連通,所以V’’中含有點(diǎn)割集V’.所以|V’||V’’||E’|=.#2024/1/27應(yīng)用離散數(shù)學(xué)第六章第2講27uv具體的構(gòu)造策略引理1引理1:設(shè)E’是邊割集,則p(G-E’)=p(G)+1.證明:如果p(G-E’)>p(G)+1,則E’不是邊割集,因?yàn)椴粷M足定義中的極小性.#說明:點(diǎn)割集無此性質(zhì)2024/1/27應(yīng)用離散數(shù)學(xué)第六章第2講28引理2引理2:設(shè)E’是非完全圖G的邊割集,(G)=|E’|,G-E’的2個(gè)連通分支是G1,G2,則存在uV(G1),vV(G2),使得(u,v)E(G)證明:(反證)否則(G)=|E’|=|V(G1)||V(G2)|

|V(G1)|+|V(G2)|-1=n-1,與G非完全圖相矛盾!#說明:a1b1(a-1)(b-1)=ab-a-b+10aba+b-1.2024/1/27應(yīng)用離散數(shù)學(xué)第六章第2講29為邊連通度任意兩點(diǎn)都連同推論推論:k-連通圖一定是k-邊連通圖.#2024/1/27應(yīng)用離散數(shù)學(xué)第六章第2講30根據(jù)Whitney定理和k-連通圖、k-邊連通圖的概念，可證自學(xué)有向圖的連通性及其分類可達(dá)；短程線；距離連通圖，強(qiáng)連通圖，弱連通圖，單向連通圖連通性判別法2024/1/27應(yīng)用離散數(shù)學(xué)第六章第2講31HasslerWhitney(1907~1989)美國數(shù)學(xué)家,曾獲得Wolf獎(jiǎng)主要研究拓?fù)鋵W(xué).20世紀(jì)30年代發(fā)表了十幾篇圖論論文,定義了“對(duì)偶圖”概念,推動(dòng)了四色定理的研究.一生的最后20年致力于數(shù)學(xué)教育,提倡應(yīng)當(dāng)讓年輕人用自己的直覺(intuition)來解決問題,而不是教一些與他們的經(jīng)驗(yàn)無關(guān)的技巧和結(jié)果.2024/1/27應(yīng)用離散數(shù)學(xué)第六章第2講32Whitney的看法應(yīng)當(dāng)讓年輕人