《路與回路》ppt課件-文庫吧
2025-04-18 18:30 本頁面
【正文】 圈，長度為 4 定理 在一個具有 n個結(jié)點的圖中，如果從結(jié)點 vj到結(jié)點 vk存在一條路，則從結(jié)點 vj到結(jié)點vk必存在一條不多于 n1條邊的路 。 證明思路：多于 n1條邊的路中必有重復(fù)出現(xiàn)的結(jié)點，反復(fù)刪去夾在兩個重復(fù)結(jié)點之間的邊之后，剩余的邊數(shù)不會超過 n1條邊 。 定理 : 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ù)要少，如此重復(fù)進(jìn)行下去，必可得到一條從 vj到 vk的不多于 n1條邊的路。 ? 定理 在一個具有 n個結(jié)點的圖中，如果從結(jié)點 vj到結(jié)點 vk存在一條路，則從結(jié)點 vj到結(jié)點 vk必存在一條邊數(shù)小于 n的通路 。 如在圖 5個結(jié)點。 v1到 v3的一條路為：v1e2v3e3v2e3v3e4v2e6v5e7v3 此路中有 6條邊，去掉 e3有路 v1e2v3e4v2e6v5e7v3 有 4條邊。 v1到 v3最短的路為 v1e2v3 二、無向圖的連通性 連通 定義 在無向 圖 G中，如果從結(jié)點 u和結(jié)點 v之間若 存在一條路，則稱結(jié)點 u和結(jié)點 v是連通的 （ connected） 。 注 ：（ 1）對于所有 v∈ V，規(guī)定結(jié)點到自身是連通的。 （ 2）由定義不難看出，無向圖中結(jié)點之間的連通關(guān)系 R={u,v|u,v∈ V且 u與 v連通 }是自反的，對稱的，傳遞的，因而 R是 V上的 等價關(guān)系 。 結(jié)點之間的連通性是結(jié)點集 V上的等價關(guān)系，對應(yīng)該等價關(guān)系，必可將作出一個劃分，把 V分成非空子集 V1, V2, … , Vm,使得兩個結(jié)點 vj和 vk是連通的，當(dāng)且僅當(dāng)它們屬于同一個 Vi 。 把子圖 G(V1) , G(V2) , … , G(Vm)稱為圖 G的 連通分支 （ connected ponents） ,圖 G的連通分支數(shù)記為 W(G) 。 例 : W(G)=3 G 見 281頁圖 練習(xí) 1：下圖中連通分支數(shù)目？ 練習(xí) 2：下圖中連通分支數(shù)目？ ?2 6? ?4 ?5 1? ?3 連通圖 定義 若圖 G只有一個連通分支，則稱 G是連通圖。否則稱 G是非連通圖或分離圖。 顯然在連通圖中，任意兩個結(jié)點之間必是連通的。 見 281頁圖 圖 (a)是連通圖 對于連通圖，常常由于刪除了圖中的點或邊，而影響了圖的連通性。 刪除結(jié)點 ：所謂在圖中刪除 結(jié)點 v， 即是把 v以及與 v關(guān)聯(lián)的邊都刪除。 刪除邊 ： 所謂在圖中刪除某條邊 ，即是把該邊刪除。 見 282頁圖 v3 v2 v1 v6 v4 (a) v5 v5 v1 v2 v3 v6 v4 (c) e v3 v2 v6 v4 (b) v5 e 割點 定義 設(shè)無向 圖 G =V,E是 連通圖 ,若有結(jié)點集 V1?V,使圖 G中 刪除了 V1的所有結(jié)點后 ,所得到的子圖是不連通圖 ,而刪除了 V1的任何真子集后 ,所得到的子圖仍是 連通圖 ,則稱
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1