路與回路ppt課件(完整版)
【正文】 圖 → 弱連通圖。 ? 三、有向圖的連通性 可達： 在無向圖 G中，從結(jié)點 u到 v若存在一條路，則稱結(jié)點 u到結(jié)點 v是可達的。 若 G連通， 可分兩步證明上式也成立： 1)先證明 ?(G)≤?(G)： 如果 G是平凡圖，則 ?(G)=0≤?(G)， 若 G是非平凡圖，則因每一結(jié)點的所有關(guān)聯(lián)邊必含一個邊割集， (因 ?(G)=min{deg(v)|v?V}，設 u?V使的deg(u)=δ(G)，與 u相關(guān)聯(lián)的 ?條邊必包含一個邊割集，至少這 ?條邊刪除使圖不連通。 2)再證 :存在結(jié)點 u和 w的每條路都通過 v ?v是割點 若連通圖 G中的某兩個結(jié)點的每一條路都通過 v，則刪去 v得到子圖 G’ ，在 G’中這兩個結(jié)點必然不連通，故 v是圖 G的割點。 見 282頁圖 v3 v2 v1 v6 v4 (a) v5 v5 v1 v2 v3 v6 v4 (c) e v3 v2 v6 v4 (b) v5 e 割點 定義 設無向 圖 G =V,E是 連通圖 ,若有結(jié)點集 V1?V,使圖 G中 刪除了 V1的所有結(jié)點后 ,所得到的子圖是不連通圖 ,而刪除了 V1的任何真子集后 ,所得到的子圖仍是 連通圖 ,則稱 V1是 G的一個 點割集 (cutset of nodes) 。 結(jié)點之間的連通性是結(jié)點集 V上的等價關(guān)系，對應該等價關(guān)系，必可將作出一個劃分，把 V分成非空子集 V1, V2, … , Vm,使得兩個結(jié)點 vj和 vk是連通的，當且僅當它們屬于同一個 Vi 。 證明思路：多于 n1條邊的路中必有重復出現(xiàn)的結(jié)點，反復刪去夾在兩個重復結(jié)點之間的邊之后，剩余的邊數(shù)不會超過 n1條邊 。 若一條路中所有的邊 e1, … , en均不相同 ,稱作跡 （ 路徑 walk） 。離散數(shù)學 Discrete Mathematics 課程回顧 圖的定義 ：結(jié)點集、邊集、圖的分類、點和邊的關(guān)聯(lián)、點與點的相鄰、邊與邊的鄰接、孤立結(jié)點、零圖、平凡圖、環(huán)、平行邊 點的度數(shù) ：度數(shù)、出度、入度、最大度、最小度、 握手定理 、相關(guān)定理 特殊的圖 ：多重圖、 簡單圖 、 完全圖 、補圖、子圖、生成子圖、圖的同構(gòu) 第七章 圖論第 2講 7— 2 路與回路 72 路與回路 在實際應用中，比如在市內(nèi)乘出租車去參觀一個博覽會，一定要司機選一條最短的路。 若一條路中所有的結(jié)點 v0, v1,… , vn均不相同 ,稱作 通路 （ Path） 。 定理 : Vs Vk Vj Vs Vs Vk Vj Vj Vk ? 定理 如果從結(jié)點 vj到 vk存在一條路，該路上的結(jié)點序列是 vj…v i…v k，如果在這條路中有 L條邊，則序列中必有 L+1個結(jié)點，若 Ln1，則必有結(jié)點 vs，它在序列中不止出現(xiàn)一次，即必有結(jié)點序列 vj…v s…v s…v k，在路中去掉從 vs到 vs的這些邊，仍是 vj到 vk的一條路，但此路比原來的路邊數(shù)要少，如此重復進行下去，必可得到一條從 vj到 vk的不多于 n1條邊的路。 把子圖 G(V1) , G(V2) , … , G(Vm)稱為圖 G的 連通分支 （ connected ponents） ,圖 G的連通分支數(shù)記為 W(G) 。 若某一個點構(gòu)成一個點割集，則稱該點為 割點 。
教學課件相關(guān)推薦
鄂ICP備17016276號-1