《路與回路》ppt課件(文件)
【正文】 分支數(shù)記為 W(G) 。 見 281頁圖 圖 (a)是連通圖 對于連通圖，常常由于刪除了圖中的點(diǎn)或邊，而影響了圖的連通性。 若某一個點(diǎn)構(gòu)成一個點(diǎn)割集，則稱該點(diǎn)為 割點(diǎn) 。 (1)若 G是平凡圖則 V1=?， k(G)=0 (2)k(Kn)=n1 (3)若圖存在割點(diǎn)，則 k(G)=1 (4)規(guī)定非連通圖的連通度 k(G)=0 v5 v1 v2 v3 v4 v5 v1 v3 v4 點(diǎn)割集 V1={v2} 一個連通 無向圖 G的結(jié)點(diǎn) v是割點(diǎn)的充分必要條件是存在兩個結(jié)點(diǎn) u和 w,使得結(jié)點(diǎn) u和 w的每一條路都通過 v 。 ? 割邊 定義 設(shè)無向 圖 G =V,E是 連通圖 ,若有邊集 E1?E，使圖 G中刪除了 E1的所有邊后，所得到的子圖是不連通圖，而刪除了 E1的任何真子集后，所得到的子圖仍是連通圖，則稱 E1是 G的一個 邊割集(cutset of edges) 。 (1)若 G是平凡圖則 E1=?， ??(G)=0 (2)若 G存在割邊，則 ?(G)=1， (3)規(guī)定非連通圖的邊連通度為 ?(G)=0 定理 對于任何一個 圖 G,有 k(G)≤ ?(G)≤ δ (G) 。 )故 ?(G)≤?(G)。對 ?(G)1條邊中的每一條邊都選取一個不同于 u， v的端點(diǎn)，把這些端點(diǎn)刪去則必至少刪去?(G)1條邊。 有向圖的可達(dá)性： 對于任何一個有向 圖G=V,E, 從結(jié)點(diǎn) u和到結(jié)點(diǎn) v有一條路 ,稱為從 u可達(dá) v。 如果從 u到 v是不可達(dá)的，則通常寫成 du,v =∞ 注意 ：當(dāng) u可達(dá) v，且 v也可達(dá) u時， du,v 不一定等于 d v, u 簡單有向圖分類（據(jù)連通性） 定義 在簡單有向 圖 G中，任何一對結(jié)點(diǎn)間，至少有一個結(jié)點(diǎn)到另一個結(jié)點(diǎn)是可達(dá)的，則稱這個圖是 單側(cè)連通 的 。而逆推均不成立。 ? ?單向連通圖判別定理 有向圖 G單向連通 ? G中有路通過每個結(jié)點(diǎn)至少一次 . 分圖 定義 在簡單有向圖中，具有強(qiáng)連通性質(zhì)的 最大子圖 ，稱為 強(qiáng)分圖 ；具有單側(cè)連通性質(zhì)的最大子圖，稱為 單側(cè)分圖 ；具有弱連通性質(zhì)的最大子圖，稱為弱分圖 。 ? 練習(xí) 28 287頁習(xí)題 說明 ：在等價關(guān)系的關(guān)系圖上，一個等價類中含有的所有元素（結(jié)點(diǎn)）恰好同在強(qiáng)分圖中。 ? 練習(xí) 72（ 2） 若無向圖 G中恰有兩個奇數(shù)度的結(jié)點(diǎn)，則這兩個結(jié)點(diǎn)之間必有一條路。如果仍是結(jié)點(diǎn) u，此路是閉跡。 ? 練習(xí) 72（ 4） 當(dāng)且僅當(dāng) G的一條邊 e不包含在 G的回路中時， e才是 G的割邊。 充分性。 ? 作業(yè) 287頁（ 3） (5) （ 8） （ 10） 選做： （ 7） 本節(jié)內(nèi)容到此結(jié)束 。因為如果連接 u和 v還有不同于邊 e的路，此路與邊 e就組成一條包含邊 e的回路，從而導(dǎo)致矛盾。設(shè) e是連通圖 G的割邊， e關(guān)聯(lián)的兩個結(jié)點(diǎn)是u和 v。繼續(xù)從 u出發(fā)，沿著該邊到達(dá)另一個結(jié)點(diǎn) u1’，依次下去直到另一個奇數(shù)度結(jié)點(diǎn)停下。 從 u開始構(gòu)造一條跡，即從 u出發(fā)經(jīng)關(guān)聯(lián)于結(jié)點(diǎn) u的邊e1到達(dá)結(jié)點(diǎn) u1，若 deg(u1)為偶數(shù)，則必可由 u1再經(jīng)關(guān)聯(lián)于結(jié)點(diǎn) u1的邊 e2到達(dá)結(jié)點(diǎn) u2，如此繼續(xù)下去，每邊只取
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1