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

第六章 圖,第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)用低。,2019/7/7,應(yīng)用離散數(shù)學(xué) 第六章 第2講,2,第六章 第2講 圖的連通性,1.通路，回路 2.連通性，點(diǎn)(邊)割集,點(diǎn)連通度,邊連通度 3. Whitney定理, 簡(jiǎn)單連通圖,之間的關(guān)系 4. 2-連通, 2-邊連通的充要條件 5. 割點(diǎn), 橋, 塊的充要條件,2019/7/7,應(yīng)用離散數(shù)學(xué) 第六章 第2講,3,通路與回路,通路，回路 簡(jiǎn)單通路，簡(jiǎn)單回路 初級(jí)通路，初級(jí)回路 初級(jí)通路判定定理,2019/7/7,應(yīng)用離散數(shù)學(xué) 第六章 第2講,4,通路和回路,通路，回路：給定圖G=.設(shè)G中頂點(diǎn)和邊的交替序列為=v0e1v1e2elvl.若滿足如下條件：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ù)目稱為的長(zhǎng)度。當(dāng)v0=vl時(shí)，稱通路為回路。,2019/7/7,應(yīng)用離散數(shù)學(xué) 第六章 第2講,5,a,f,b,c,g,h,i,e,d,通路和回路,簡(jiǎn)單通路：若中所有邊各異； 簡(jiǎn)單回路：類似； 初級(jí)通路（路徑）：若中所有頂點(diǎn)各異，所有邊也各異； 初級(jí)回路（圈）：類似； 奇圈，偶圈：圈的長(zhǎng)度為奇數(shù)或偶數(shù)。 復(fù)雜通路： 中有邊重復(fù)出現(xiàn)； 復(fù)雜回路：類似,2019/7/7,應(yīng)用離散數(shù)學(xué) 第六章 第2講,6,通路和回路,回路是通路的特殊情況； 初級(jí)通路（回路）是簡(jiǎn)單通路（回路），但反之不真； (頂點(diǎn)各異且邊各異則邊各異；反之不然) 通路的表示法： 頂點(diǎn)和邊的交替序列表示法； 邊序列； 在簡(jiǎn)單圖中，可以用頂點(diǎn)序列,2019/7/7,應(yīng)用離散數(shù)學(xué) 第六章 第2講,7,通路和回路,定理3：在一個(gè)n階圖中，若從頂點(diǎn)u到v（u和v不等）存在通路，則從u到v存在長(zhǎng)度小于等于n-1的初級(jí)通路。 證明：最多該通路中有n個(gè)頂點(diǎn)，如果n個(gè)頂點(diǎn)互不相同（初級(jí)通路），則最多為n-1條邊。,2019/7/7,應(yīng)用離散數(shù)學(xué) 第六章 第2講,8,通路和回路,定理4：在一個(gè)n階圖中，如果存在v到自身的簡(jiǎn)單回路，則從v到自身存在長(zhǎng)度不超過n的初級(jí)回路。 證明：類似。,2019/7/7,應(yīng)用離散數(shù)學(xué) 第六章 第2講,9,連通性,無向圖的連通性：在無向圖G中，若頂點(diǎn)v1和v2之間存在通路，則稱v1與v2是連通的。規(guī)定v1與自身是連通的。 連通圖：若無向圖G是平凡圖，或G中任意兩頂點(diǎn)都是連通的，則稱G是連通圖。否則稱G為非連通圖。,2019/7/7,應(yīng)用離散數(shù)學(xué) 第六章 第2講,10,平凡圖,任意兩頂點(diǎn)都是連通的,連通分支,連通關(guān)系：設(shè)G=為一無向圖，設(shè) R=| x, yV且x與y連通 則R是自反的，對(duì)稱的，并且是傳遞的，因而R是V上的等價(jià)關(guān)系。 連通分支：設(shè)R的不同等價(jià)類分別為V1，Vk,稱它們的導(dǎo)出子圖GV1，GVk 為G的連通分支，其連通分支的個(gè)數(shù)記為p(G)。 若p(G)=1，則G是連通圖。,2019/7/7,應(yīng)用離散數(shù)學(xué) 第六章 第2講,11,圖中點(diǎn)之間的距離,短程線：若兩點(diǎn)是連通的，則稱兩點(diǎn)之間的長(zhǎng)度最短的通路為兩點(diǎn)之間的短程線。 距離：短程線的長(zhǎng)度稱為兩點(diǎn)之間的距離，記為d(v1,v2)。,2019/7/7,應(yīng)用離散數(shù)學(xué) 第六章 第2講,12,兩個(gè)連通分支,如何定義連通度,問題: 如何定量比較無向圖連通性的強(qiáng)與弱?,2019/7/7,應(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),即“變得更加不連通”,2019/7/7,應(yīng)用離散數(shù)學(xué) 第六章 第2講,14,連通分支的個(gè)數(shù),割集(cutset),點(diǎn)割集(vertex cut) 邊割集(edge cut) 割點(diǎn)(cut vertex) 割邊(cut edge)(橋)(bridge),2019/7/7,應(yīng)用離散數(shù)學(xué) 第六章 第2講,15,點(diǎn)割集(vertex cutset),點(diǎn)割集: 無向圖G=, VV, 滿足 (1) p(G-V)p(G); (2) 極小性: VV, p(G-V)=p(G), 則稱V為點(diǎn)割集. 說明: “極小性”是為了保證點(diǎn)割集概念的非平凡性,2019/7/7,應(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,2019/7/7,應(yīng)用離散數(shù)學(xué) 第六章 第2講,17,a,b,c,d,f,e,g,h,k,j,i,a,b,c,e,f,d,j,i,g,h,k,G1,G2,Question?,割點(diǎn)(cut-point / cut-vertex),割點(diǎn): v是割點(diǎn) v是割集 例: G1中f是割點(diǎn), G2中無割點(diǎn),2019/7/7,應(yīng)用離散數(shù)學(xué) 第六章 第2講,18,a,b,c,d,f,e,g,h,k,j,i,a,b,c,e,f,d,j,i,g,h,k,G1,G2,邊割集(edge cutset),邊割集: 無向圖G=, EE, 滿足 (1) p(G-E)p(G); (2) 極小性: EE, p(G-E)=p(G), 則稱E為邊割集. 說明: “極小性”是為了保證邊割集概念的非平凡性,2019/7/7,應(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),2019/7/7,應(yīng)用離散數(shù)學(xué) 第六章 第2講,20,a,b,c,d,f,e,g,h,k,j,i,a,b,c,e,f,d,j,i,g,h,k,G1,G2,注意：極小性,割邊(cut-edge)(橋),割邊: (u,v)是割邊(橋) (u,v)是邊割集 例: G1中(f,g)是橋, G2中無橋,2019/7/7,應(yīng)用離散數(shù)學(xué) 第六章 第2講,21,a,b,c,d,f,e,l,h,k,j,i,a,b,c,e,f,d,j,i,g,h,k,G1,G2,g,扇形割集(fan cutset),IG(v)不一定是邊割集(不一定極小) IG(v)不是邊割集 v是割點(diǎn) 扇形割集: E是邊割集EIG(v) 例: (a,g),(a,b),(g,a),(g,b),(g,c),(c,d), (d,e),(d,f), (a,b),(g,b),(g,c),2019/7/7,應(yīng)用離散數(shù)學(xué) 第六章 第2講,22,a,b,c,g,d,f,e,?,關(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)=4,2019/7/7,應(yīng)用離散數(shù)學(xué) 第六章 第2講,23,G,H,F,邊連通度(edge-connectivity),邊連通度: G是無向連通圖, (G) = min |E| | E是G的邊割集 規(guī)定: G非連通: (G)=0 例: (G)=1, (H)=2, (F)=3, (K5)=4,2019/7/7,應(yīng)用離散數(shù)學(xué) 第六章 第2講,24,G,H,F,k-連通圖, k-邊連通圖,k-連通圖(k-connected): (G)k k-邊連通圖(k-edge-connected): (G)k 例: 彼得森圖 =3, =3; 它是1-連通圖, 2-連通圖,3-連通圖, 但不是4-連通圖; 它是1-邊連通圖, 2-邊連通圖,3-邊連通圖,但不是4-邊連通圖,2019/7/7,應(yīng)用離散數(shù)學(xué) 第六章 第2講,25,點(diǎn)連通度,邊連通度,Whitney定理,定理10: . 證明: 不妨設(shè)G是3階以上連通簡(jiǎn)單非完全圖. () 設(shè)d(v)=, 則|IG(v)|=, IG(v)中一定有邊割集E, 所以|E|IG(v)|=. () 設(shè)E是邊割集,|E|=,從V(E)中找出點(diǎn)割集V,使得|V|, 所以|V|.,2019/7/7,應(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-VG-E=G1G2, u和v在G-V中不連通, 所以V中含有點(diǎn)割集V. 所以 |V|V|E|=. #,2019/7/7,應(yīng)用離散數(shù)學(xué) 第六章 第2講,27,u,v,具體的構(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ì),2019/7/7,應(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+10 aba+b-1.,2019/7/7,應(yīng)用離散數(shù)學(xué) 第六章 第2講,29,為邊連通度,任意兩點(diǎn)都連同,推論,推論: k-連通圖一定是k-邊連通圖. #,2019/7/7,應(yīng)用離散數(shù)學(xué) 第六章 第2講,30,根據(jù)Whitney定理和k-連通圖、k-邊連通圖的概念，可證,自學(xué),有向圖的連通性及其分類 可達(dá)； 短程線；距離 連通圖，強(qiáng)連通圖，弱連通圖，單向連通圖 連通性判別法,2019/7/7,應(yīng)用離散數(shù)學(xué) 第六章 第2講,31,Hassler Whitney(19071989),美國(guó)數(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é)果.,2019/7/7,應(yīng)用離散數(shù)學(xué) 第六章 第2講,32,Whitney的看法,應(yīng)當(dāng)讓年輕人用自己的直覺(intuition)來解決問題,而不是教一些與他們的經(jīng)驗(yàn)無關(guān)的技巧和結(jié)果. 什么是直覺?-習(xí)慣成自然,熟能生巧 騎自行車: “平衡感” 游泳: “水感” 學(xué)外語(yǔ): “語(yǔ)感” 如何取得經(jīng)驗(yàn)?-自己動(dòng)手 練習(xí)! 不能只聽不做.,2019/7/7,應(yīng)用離散數(shù)學(xué) 第六章 第2講,33,積累經(jīng)驗(yàn),割點(diǎn)的充分必要條件,定理11: 無向連通圖G中頂點(diǎn)v是割點(diǎn) 可以把V(G)-v劃分成V1與V2,使得從V1中任意頂點(diǎn)u到V2中任意頂點(diǎn)w的路徑都要經(jīng)過v. #,2019/7/7,應(yīng)用離散數(shù)學(xué) 第六