路與回路ppt課件(參考版)
2025-05-06 18:30本頁面
【正文】 ? 作業(yè) 287頁（ 3） (5) （ 8） （ 10） 選做： （ 7） 本節(jié)內(nèi)容到此結(jié)束 。因為如果連接 u和 v還有不同于邊 e的路，此路與邊 e就組成一條包含邊 e的回路，從而導致矛盾。 充分性。設(shè) e是連通圖 G的割邊， e關(guān)聯(lián)的兩個結(jié)點是u和 v。 ? 練習 72（ 4） 當且僅當 G的一條邊 e不包含在 G的回路中時， e才是 G的割邊。繼續(xù)從 u出發(fā)，沿著該邊到達另一個結(jié)點 u1’，依次下去直到另一個奇數(shù)度結(jié)點停下。如果仍是結(jié)點 u，此路是閉跡。 從 u開始構(gòu)造一條跡，即從 u出發(fā)經(jīng)關(guān)聯(lián)于結(jié)點 u的邊e1到達結(jié)點 u1，若 deg(u1)為偶數(shù)，則必可由 u1再經(jīng)關(guān)聯(lián)于結(jié)點 u1的邊 e2到達結(jié)點 u2，如此繼續(xù)下去，每邊只取一次，直到另一個奇數(shù)度結(jié)點停止，由于圖 G中只有兩個奇數(shù)度結(jié)點，故該結(jié)點或是 u或是 v。 ? 練習 72（ 2） 若無向圖 G中恰有兩個奇數(shù)度的結(jié)點，則這兩個結(jié)點之間必有一條路。 練習 72（ 1） 在無向圖 G中，從結(jié)點 u到結(jié)點 v有一條長度為偶數(shù)的通路，從結(jié)點 u到結(jié)點 v又有一條長度為奇數(shù)的通路，則在 G中必有一條長度為奇數(shù)的回路。 ? 練習 28 287頁習題 說明 ：在等價關(guān)系的關(guān)系圖上，一個等價類中含有的所有元素（結(jié)點）恰好同在強分圖中。 ?證明思路： 1)先證 :每一個結(jié)點 必 位于一個強分圖中。 ? ?單向連通圖判別定理 有向圖 G單向連通 ? G中有路通過每個結(jié)點至少一次 . 分圖 定義 在簡單有向圖中，具有強連通性質(zhì)的 最大子圖 ，稱為 強分圖 ；具有單側(cè)連通性質(zhì)的最大子圖，稱為 單側(cè)分圖 ；具有弱連通性質(zhì)的最大子圖，稱為弱分圖 。 定理 (強連通圖判別定理 ) 一個有向圖是強連通的充要條件是 G有一個回路，它至少包含每個結(jié)點一次。而逆推均不成立。如果在圖 G中略去邊的方向，將它看成無向圖后，圖是連通的，則稱該圖為弱連通 的。 如果從 u到 v是不可達的，則通常寫成 du,v =∞ 注意 ：當 u可達 v，且 v也可達 u時， du,v 不一定等于 d v, u 簡單有向圖分類（據(jù)連通性） 定義 在簡單有向 圖 G中，任何一對結(jié)點間，至少有一個結(jié)點到另一個結(jié)點是可達的，則稱這個圖是 單側(cè)連通 的 。故可達性不是等價關(guān)系。 有向圖的可達性： 對于任何一個有向 圖G=V,E, 從結(jié)點 u和到結(jié)點 v有一條路 ,稱為從 u可達 v。由 1)和 2)得 k(G)≤?(G)≤?(G)。對 ?(G)1條邊中的每一條邊都選取一個不同于 u， v的端點，把這些端點刪去則必至少刪去?(G)1條邊。 2)再證 k(G)≤?(G)： (a)設(shè) ?(G)=1，即 G有一割邊，顯然這時 k(G)=l，上式成立。 )故 ?(G)≤?(G)。 282頁 圖 k(G)=1,?(G)=1,?(G)=1 例 : s a b c d a k(G)=1,?(G)=2,?(G)=2 ? 證明 若 G不連通，則 k(G)=?(G)=0，故上式成立。 (1)若 G是平凡圖則 E1=?， ??(G)=0 (2)若 G存在割邊，則 ?(G)=1， (3)規(guī)定非連通圖的邊連通度為 ?(G)=0 定理 對于任何一個 圖 G,有 k(G)≤ ?(G)≤ δ (G) 。 割邊 e使圖 G滿足 W(Ge)W(G
教學課件相關(guān)推薦
鄂ICP備17016276號-1