應(yīng)用離散數(shù)學第六章第2講省名師優(yōu)質(zhì)課賽課獲獎?wù)n件市賽課一等獎?wù)n件

第六章圖第2講圖連通性第1頁通信網(wǎng)絡(luò)圖論應(yīng)用一個主要方面就是通信網(wǎng)絡(luò)。如電話網(wǎng)絡(luò)、計算機網(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ò)中各個用戶能夠快速安全地傳遞信息，不產(chǎn)生差錯和故障，同時使建造和維護網(wǎng)絡(luò)所需費用低。2023/9/13應(yīng)用離散數(shù)學第六章第2講2第2頁第六章第2講圖連通性1.通路，回路2.連通性，點(邊)割集,點連通度

,邊連通度

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

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

V’’V’,p(G-V’’)=p(G),則稱V’為點割集.說明:“極小性”是為了確保點割集概念非平凡性2023/9/13應(yīng)用離散數(shù)學第六章第2講16第16頁點割集(舉例)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}2023/9/13應(yīng)用離散數(shù)學第六章第2講17abcdfeghkjiabcefdjighkG1G2Question?第17頁割點(cut-point/cut-vertex)割點:v是割點

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

E’’E’,p(G-E’’)=p(G),則稱E’為邊割集.說明:“極小性”是為了確保邊割集概念非平凡性2023/9/13應(yīng)用離散數(shù)學第六章第2講19第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)}2023/9/13應(yīng)用離散數(shù)學第六章第2講20abcdfeghkjiabcefdjighkG1G2注意：極小性第20頁割邊(cut-edge)(橋)割邊:(u,v)是割邊(橋)

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

v是割點扇形割集: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)}2023/9/13應(yīng)用離散數(shù)學第六章第2講22abcgdfe???關(guān)聯(lián)集:IG(v)={e|e與v關(guān)聯(lián)

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

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

)設(shè)E’是邊割集,|E’|=,從V(E’)中找出點割集V’,使得|V’|,所以|V’|.2023/9/13應(yīng)用離散數(shù)學第六章第2講26為圖最小度。為點連通度為邊連通度第26頁Whitney定理(續(xù))證實(續(xù)):()設(shè)G-E’2個連通分支是G1,G2.設(shè)uV(G1),vV(G2),使得(u,v)E(G).以下結(jié)構(gòu)V’’:eE’,選擇e異于u,v一個端點放入V’’.|V’’||E’|.G-V’’G-E’=G1G2,u和v在G-V’’中不連通,所以V’’中含有點割集V’.所以|V’||V’’||E’|=.#2023/9/13應(yīng)用離散數(shù)學第六章第2講27uv詳細結(jié)構(gòu)策略第27頁引理1引理1:設(shè)E’是邊割集,則p(G-E’)=p(G)+1.證實:假如p(G-E’)>p(G)+1,則E’不是邊割集,因為不滿足定義中極小性.#說明:點割集無此性質(zhì)2023/9/13應(yīng)用離散數(shù)學第六章第2講28第28頁引理2引理2:設(shè)E’是非完全圖G邊割集,(G)=|E’|,G-E’2個連通分支是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.2023/9/13應(yīng)用離散數(shù)學第六章第2講29為邊連通度任意兩點都連同第29頁推論推論:k-連通圖一定是k-邊連通圖.#2023/9/13應(yīng)用離散數(shù)學第六章第2講30依據(jù)Whitney定理和k-連通圖、k-邊連通圖概念，可證第30頁自學有向圖連通性及其分類可達；短程線；距離連通圖，強連通圖，弱連通圖，單向連通圖連通性判別法2023/9/13應(yīng)用離散數(shù)學第六章第2講31第31頁HasslerWhitney(1907~1989)美國數(shù)學家,曾取得Wolf獎主要研究拓撲學.20世紀30年代發(fā)表了十幾篇圖論論文,定義了“對偶圖”概念,推進了四色定理研究.一生最終致力于數(shù)學教育,提倡應(yīng)該讓年輕人用自己直覺(intuition)來處理問題,而不是教一些與他們經(jīng)驗無關(guān)技巧和結(jié)果.2023/9/13應(yīng)用離散數(shù)學第六章第2講32第32頁Whitney看法應(yīng)該讓年輕人用