應(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)用低 2020 2 3 應(yīng)用離散數(shù)學(xué)第六章第2講 2 第六章第2講圖的連通性 1 通路 回路2 連通性 點(diǎn) 邊 割集 點(diǎn)連通度 邊連通度 3 Whitney定理 簡單連通圖 之間的關(guān)系4 2 連通 2 邊連通的充要條件5 割點(diǎn) 橋 塊的充要條件 2020 2 3 應(yīng)用離散數(shù)學(xué)第六章第2講 3 通路與回路 通路 回路簡單通路 簡單回路初級通路 初級回路初級通路判定定理 2020 2 3 應(yīng)用離散數(shù)學(xué)第六章第2講 4 通路和回路 通路 回路 給定圖G 設(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í) 稱通路為回路 2020 2 3 應(yīng)用離散數(shù)學(xué)第六章第2講 5 a f b c g h i e d 通路和回路 簡單通路 若 中所有邊各異 簡單回路 類似 初級通路 路徑 若 中所有頂點(diǎn)各異 所有邊也各異 初級回路 圈 類似 奇圈 偶圈 圈的長度為奇數(shù)或偶數(shù) 復(fù)雜通路 中有邊重復(fù)出現(xiàn) 復(fù)雜回路 類似 2020 2 3 應(yīng)用離散數(shù)學(xué)第六章第2講 6 通路和回路 回路是通路的特殊情況 初級通路 回路 是簡單通路 回路 但反之不真 頂點(diǎn)各異且邊各異則邊各異 反之不然 通路的表示法 頂點(diǎn)和邊的交替序列表示法 邊序列 在簡單圖中 可以用頂點(diǎn)序列 2020 2 3 應(yīng)用離散數(shù)學(xué)第六章第2講 7 通路和回路 定理3 在一個(gè)n階圖中 若從頂點(diǎn)u到v u和v不等 存在通路 則從u到v存在長度小于等于n 1的初級通路 證明 最多該通路中有n個(gè)頂點(diǎn) 如果n個(gè)頂點(diǎn)互不相同 初級通路 則最多為n 1條邊 2020 2 3 應(yīng)用離散數(shù)學(xué)第六章第2講 8 通路和回路 定理4 在一個(gè)n階圖中 如果存在v到自身的簡單回路 則從v到自身存在長度不超過n的初級回路 證明 類似 2020 2 3 應(yīng)用離散數(shù)學(xué)第六章第2講 9 連通性 無向圖的連通性 在無向圖G中 若頂點(diǎn)v1和v2之間存在通路 則稱v1與v2是連通的 規(guī)定v1與自身是連通的 連通圖 若無向圖G是平凡圖 或G中任意兩頂點(diǎn)都是連通的 則稱G是連通圖 否則稱G為非連通圖 2020 2 3 應(yīng)用離散數(shù)學(xué)第六章第2講 10 平凡圖 任意兩頂點(diǎn)都是連通的 連通分支 連通關(guān)系 設(shè)G 為一無向圖 設(shè)R x y V且x與y連通 則R是自反的 對稱的 并且是傳遞的 因而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是連通圖 2020 2 3 應(yīng)用離散數(shù)學(xué)第六章第2講 11 圖中點(diǎn)之間的距離 短程線 若兩點(diǎn)是連通的 則稱兩點(diǎn)之間的長度最短的通路為兩點(diǎn)之間的短程線 距離 短程線的長度稱為兩點(diǎn)之間的距離 記為d v1 v2 2020 2 3 應(yīng)用離散數(shù)學(xué)第六章第2講 12 兩個(gè)連通分支 如何定義連通度 問題 如何定量比較無向圖連通性的強(qiáng)與弱 2020 2 3 應(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 即 變得更加不連通 2020 2 3 應(yīng)用離散數(shù)學(xué)第六章第2講 14 連通分支的個(gè)數(shù) 割集 cutset 點(diǎn)割集 vertexcut 邊割集 edgecut 割點(diǎn) cutvertex 割邊 cutedge 橋 bridge 2020 2 3 應(yīng)用離散數(shù)學(xué)第六章第2講 15 點(diǎn)割集 vertexcutset 點(diǎn)割集 無向圖G V V 滿足 1 p G V p G 2 極小性 V V p G V p G 則稱V 為點(diǎn)割集 說明 極小性 是為了保證點(diǎn)割集概念的非平凡性 2020 2 3 應(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 2020 2 3 應(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) 2020 2 3 應(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 邊割集 edgecutset 邊割集 無向圖G E E 滿足 1 p G E p G 2 極小性 E E p G E p G 則稱E 為邊割集 說明 極小性 是為了保證邊割集概念的非平凡性 2020 2 3 應(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 2020 2 3 應(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中無橋 2020 2 3 應(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 扇形割集 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 2020 2 3 應(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 2020 2 3 應(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 2020 2 3 應(yīng)用離散數(shù)學(xué)第六章第2講 24 G H F k 連通圖 k 邊連通圖 k 連通圖 k connected G kk 邊連通圖 k edge connected G k例 彼得森圖 3 3 它是1 連通圖 2 連通圖 3 連通圖 但不是4 連通圖 它是1 邊連通圖 2 邊連通圖 3 邊連通圖 但不是4 邊連通圖 2020 2 3 應(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 2020 2 3 應(yīng)用離散數(shù)學(xué)第六章第2講 26 為圖的最小度 為點(diǎn)連通度 為邊連通度 Whitney定理 續(xù) 證明 續(xù) 設(shè)G E 的2個(gè)連通分支是G1 G2 設(shè)u V G1 v V G2 使得 u v E G 如下構(gòu)造V e E 選擇e的異于u v的一個(gè)端點(diǎn)放入V V E G V G E G1 G2 u和v在G V 中不連通 所以V 中含有點(diǎn)割集V 所以 V V E 2020 2 3 應(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ì) 2020 2 3 應(yīng)用離散數(shù)學(xué)第六章第2講 28 引理2 引理2 設(shè)E 是非完全圖G的邊割集 G E G E 的2個(gè)連通分支是G1 G2 則存在u V G1 v V G2 使得 u v E G 證明 反證 否則 G E V G1 V G2 V G1 V G2 1 n 1 與G非完全圖相矛盾 說明 a 1 b 1 a 1 b 1 ab a b 1 0 ab a b 1 2020 2 3 應(yīng)用離散數(shù)學(xué)第六章第2講 29 為邊連通度 任意兩點(diǎn)都連同 推論 推論 k 連通圖一定是k 邊連通圖 2020 2 3 應(yīng)用離散數(shù)學(xué)第六章第2講 30 根據(jù)Whitney定理和k 連通圖 k 邊連通圖的概念 可證 自學(xué) 有向圖的連通性及其分類可達(dá) 短程線 距離連通圖 強(qiáng)連通圖 弱連通圖 單向連通圖連通性判別法 2020 2 3 應(yīng)用離散數(shù)學(xué)第六章第2講 31 HasslerWhitney 1907 1989 美國數(shù)學(xué)家 曾獲得Wolf獎(jiǎng)主要研究拓?fù)鋵W(xué) 20世紀(jì)30年代發(fā)表了十幾篇圖論論文 定義了 對偶圖 概念 推動(dòng)了四色定理的研究 一生的最后20年致力于數(shù)學(xué)教育 提倡應(yīng)當(dāng)讓年輕人用自己的直覺 intuition 來解決問題 而不是教一些與他們的經(jīng)驗(yàn)無關(guān)的技巧和結(jié)果 2020 2 3 應(yīng)用離散數(shù)學(xué)第六章第2講 32 Whitney的看法 應(yīng)當(dāng)讓年輕人用自己的直覺 intuition 來解決問題 而不是教一些與他們的經(jīng)驗(yàn)無關(guān)的技巧和結(jié)果 什么是直覺 習(xí)慣成自然 熟能生巧騎自行車 平衡感 游泳 水感 學(xué)外語 語感 如何取得經(jīng)驗(yàn) 自己動(dòng)手練習(xí) 不能只聽不做 2020 2 3 應(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 2020 2 3 應(yīng)用離散數(shù)學(xué)第六章第2講 34