應用離散數(shù)學第六章第講

應用離散數(shù)學第六章第講第1頁，共36頁，2023年，2月20日，星期六通信網(wǎng)絡圖論應用的一個重要方面就是通信網(wǎng)絡。如電話網(wǎng)絡、計算機網(wǎng)絡、管理信息系統(tǒng)、醫(yī)療數(shù)據(jù)網(wǎng)絡、銀行數(shù)據(jù)網(wǎng)絡、開關網(wǎng)絡等。這些網(wǎng)絡的基本要求是網(wǎng)絡中的各個用戶能夠快速安全地傳遞信息，不產(chǎn)生差錯和故障，同時使建造和維護網(wǎng)絡所需費用低。2023/4/21應用離散數(shù)學第六章第2講2第2頁，共36頁，2023年，2月20日，星期六第六章第2講圖的連通性1.通路，回路2.連通性，點(邊)割集,點連通度,邊連通度3.Whitney定理,簡單連通圖,,之間的關系4.2-連通,2-邊連通的充要條件5.割點,橋,塊的充要條件2023/4/21應用離散數(shù)學第六章第2講3第3頁，共36頁，2023年，2月20日，星期六通路與回路通路，回路簡單通路，簡單回路初級通路，初級回路初級通路判定定理2023/4/21應用離散數(shù)學第六章第2講4第4頁，共36頁，2023年，2月20日，星期六通路和回路通路，回路：給定圖G=<V,E>.設G中頂點和邊的交替序列為Γ=v0e1v1e2…elvl.若Γ滿足如下條件：vi-1是ei端點（G為有向圖時，要求vi-1是ei起始點，vi是ei的終點），則稱Γ為v0到vl的通路。v0和vl分別稱為此通路的起點和終點。Γ中所含邊的數(shù)目稱為Γ的長度。當v0=vl時，稱通路為回路。2023/4/21應用離散數(shù)學第六章第2講5afbcghied第5頁，共36頁，2023年，2月20日，星期六通路和回路簡單通路：若Γ中所有邊各異；簡單回路：類似；初級通路（路徑）：若Γ中所有頂點各異，所有邊也各異；初級回路（圈）：類似；奇圈，偶圈：圈的長度為奇數(shù)或偶數(shù)。復雜通路：Γ中有邊重復出現(xiàn)；復雜回路：類似2023/4/21應用離散數(shù)學第六章第2講6第6頁，共36頁，2023年，2月20日，星期六通路和回路回路是通路的特殊情況；初級通路（回路）是簡單通路（回路），但反之不真；

(頂點各異且邊各異則邊各異；反之不然)通路的表示法：頂點和邊的交替序列表示法；邊序列；在簡單圖中，可以用頂點序列2023/4/21應用離散數(shù)學第六章第2講7第7頁，共36頁，2023年，2月20日，星期六通路和回路定理3：在一個n階圖中，若從頂點u到v（u和v不等）存在通路，則從u到v存在長度小于等于n-1的初級通路。證明：最多該通路中有n個頂點，如果n個頂點互不相同（初級通路），則最多為n-1條邊。2023/4/21應用離散數(shù)學第六章第2講8第8頁，共36頁，2023年，2月20日，星期六通路和回路定理4：在一個n階圖中，如果存在v到自身的簡單回路，則從v到自身存在長度不超過n的初級回路。證明：類似。2023/4/21應用離散數(shù)學第六章第2講9第9頁，共36頁，2023年，2月20日，星期六連通性無向圖的連通性：在無向圖G中，若頂點v1和v2之間存在通路，則稱v1與v2是連通的。規(guī)定v1與自身是連通的。連通圖：若無向圖G是平凡圖，或G中任意兩頂點都是連通的，則稱G是連通圖。否則稱G為非連通圖。2023/4/21應用離散數(shù)學第六章第2講10平凡圖任意兩頂點都是連通的第10頁，共36頁，2023年，2月20日，星期六連通分支連通關系：設G=<V,E>為一無向圖，設

R={<x,y>|x,y∈V且x與y連通}

則R是自反的，對稱的，并且是傳遞的，因而R是V上的等價關系。連通分支：設R的不同等價類分別為V1，…，Vk,稱它們的導出子圖G[V1]，…，G[Vk]為G的連通分支，其連通分支的個數(shù)記為p(G)。若p(G)=1，則G是連通圖。2023/4/21應用離散數(shù)學第六章第2講11第11頁，共36頁，2023年，2月20日，星期六圖中點之間的距離短程線：若兩點是連通的，則稱兩點之間的長度最短的通路為兩點之間的短程線。距離：短程線的長度稱為兩點之間的距離，記為d(v1,v2)。2023/4/21應用離散數(shù)學第六章第2講12兩個連通分支第12頁，共36頁，2023年，2月20日，星期六如何定義連通度問題:如何定量比較無向圖連通性的強與弱?2023/4/21應用離散數(shù)學第六章第2講13試想？？第13頁，共36頁，2023年，2月20日，星期六如何定義連通度點連通度:為了破壞連通性,至少需要刪除多少個頂點?邊連通度:為了破壞連通性,至少需要刪除多少條邊?說明:“破壞連通性”指p(G-V’)>p(G),或p(G-E’)>p(G),即“變得更加不連通”2023/4/21應用離散數(shù)學第六章第2講14連通分支的個數(shù)第14頁，共36頁，2023年，2月20日，星期六割集(cutset)點割集(vertexcut)邊割集(edgecut)割點(cutvertex)割邊(cutedge)(橋)(bridge)2023/4/21應用離散數(shù)學第六章第2講15第15頁，共36頁，2023年，2月20日，星期六點割集(vertexcutset)點割集:無向圖G=<V,E>,V’V,滿足

(1)p(G-V’)>p(G);(2)極小性:V’’V’,p(G-V’’)=p(G),則稱V’為點割集.說明:“極小性”是為了保證點割集概念的非平凡性2023/4/21應用離散數(shù)學第六章第2講16第16頁，共36頁，2023年，2月20日，星期六點割集(舉例)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/4/21應用離散數(shù)學第六章第2講17abcdfeghkjiabcefdjighkG1G2Question?第17頁，共36頁，2023年，2月20日，星期六割點(cut-point/cut-vertex)割點:v是割點{v}是割集例:G1中f是割點,G2中無割點2023/4/21應用離散數(shù)學第六章第2講18abcdfeghkjiabcefdjighkG1G2第18頁，共36頁，2023年，2月20日，星期六邊割集(edgecutset)邊割集:無向圖G=<V,E>,E’E,滿足

(1)p(G-E’)>p(G);(2)極小性:E’’E’,p(G-E’’)=p(G),則稱E’為邊割集.說明:“極小性”是為了保證邊割集概念的非平凡性2023/4/21應用離散數(shù)學第六章第2講19第19頁，共36頁，2023年，2月20日，星期六邊割集(舉例)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/4/21應用離散數(shù)學第六章第2講20abcdfeghkjiabcefdjighkG1G2注意：極小性第20頁，共36頁，2023年，2月20日，星期六割邊(cut-edge)(橋)割邊:(u,v)是割邊(橋){(u,v)}是邊割集例:G1中(f,g)是橋,G2中無橋2023/4/21應用離散數(shù)學第六章第2講21abcdfelhkjiabcefdjighkG1G2g第21頁，共36頁，2023年，2月20日，星期六扇形割集(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/4/21應用離散數(shù)學第六章第2講22abcgdfe???關聯(lián)集:IG(v)={e|e與v關聯(lián)}割點割點第22頁，共36頁，2023年，2月20日，星期六點連通度(vertex-connectivity)點連通度:G是無向連通非完全圖,(G)=min{|V’||V’是G的點割集}規(guī)定:(Kn)=n-1,G非連通:(G)=0例:(G)=1,(H)=2,(F)=3,(K5)=42023/4/21應用離散數(shù)學第六章第2講23GHF第23頁，共36頁，2023年，2月20日，星期六邊連通度(edge-connectivity)邊連通度:G是無向連通圖,(G)=min{|E’||E’是G的邊割集}規(guī)定:G非連通:(G)=0例:(G)=1,(H)=2,(F)=3,(K5)=42023/4/21應用離散數(shù)學第六章第2講24GHF第24頁，共36頁，2023年，2月20日，星期六k-連通圖,k-邊連通圖k-連通圖(k-connected):(G)kk-邊連通圖(k-edge-connected):(G)k例:彼得森圖=3,=3;它是1-連通圖,2-連通圖,3-連通圖,但不是4-連通圖;它是1-邊連通圖,2-邊連通圖,3-邊連通圖,但不是4-邊連通圖2023/4/21應用離散數(shù)學第六章第2講25點連通度邊連通度第25頁，共36頁，2023年，2月20日，星期六Whitney定理定理10:.證明:不妨設G是3階以上連通簡單非完全圖.()設d(v)=,則|IG(v)|=,IG(v)中一定有邊割集E’,所以|E’||IG(v)|=.()設E’是邊割集,|E’|=,從V(E’)中找出點割集V’,使得|V’|,所以|V’|.2023/4/21應用離散數(shù)學第六章第2講26為圖的最小度。為點連通度為邊連通度第26頁，共36頁，2023年，2月20日，星期六Whitney定理(續(xù))證明(續(xù)):()設G-E’的2個連通分支是G1,G2.設uV(G1),vV(G2),使得(u,v)E(G).如下構造V’’:eE’,選擇e的異于u,v的一個端點放入V’’.|V’’||E’|.G-V’’G-E’=G1G2,u和v在G-V’’中不連通,所以V’’中含有點割集V’.

所以|V’||V’’||E’|=.#2023/4/21應用離散數(shù)學第六章第2講27uv具體的構造策略第27頁，共36頁，2023年，2月20日，星期六引理1引理1:設E’是邊割集,則p(G-E’)=p(G)+1.證明:如果p(G-E’)>p(G)+1,則E’不是邊割集,因為不滿足定義中的極小性.#說明:點割集無此性質(zhì)2023/4/21應用離散數(shù)學第六章第2講28第28頁，共36頁，2023年，2月20日，星期六引理2引理2:設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/4/21應用離散數(shù)學第六章第2講29為邊連通度任意兩點都連同第29頁，共36頁，2023年，2月20日，星期六推論推論:k-連通圖一定是k-邊連通圖.#2023/4/21應用離散數(shù)學第六章第2講30根據(jù)Whitney定理和k-連通圖、k-邊連通圖的概念，可證第30頁，共36頁，2023年，2月20日，星期六自學有向圖的連通性及其分類可達；短程線；距離連通圖，強連通圖，弱連通圖，單向連通圖連通性判別法2023/4/21應用離散數(shù)學第六章第2講31第31頁，共36頁，2023年，2月20日，星期六HasslerWhitney(1907~1989)美國數(shù)學家,曾獲得Wolf獎主要研究拓撲學.20世紀30年代發(fā)表了十幾篇圖論論文,定義了“對偶圖”概念,推動了四色定理的研究.一生的最后20年致力于數(shù)學教育,提倡應當讓年輕人用自己的直覺(intuition)來解決問題,而不是教一些與他們的經(jīng)驗無關的技巧和結果.2023/4/21應用離散數(shù)學第六章第2講32第32頁，共36頁，2023年，2月20日，星期六Whitney的看法應當讓年輕人用自己的直覺(int