圖論28電子科大楊春(編輯修改稿)
2025-01-20 13:42 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 x t 0 1 2 ?1 ? 0 1 n “充分性” 不失一般性，設(shè) C= v1→v 2→…→v n→v 1是包含 D的所有頂點(diǎn)的一條回路。對(duì)于 D的任意兩點(diǎn) vi與 vj(ij) ,一方面，由 C可得到 vi到 vj的途徑 vi →v i+1 →… →v j。另一方面，由 C又可得到 vj到 vi的途徑 vj →v j+1 →…v i1 →v i。所以 D中任意兩點(diǎn)是強(qiáng)連通的，即 D是強(qiáng)連通圖。 例 2 說(shuō)明下圖 D是強(qiáng)連通圖。 v1 v5 v4 v2 v3 v6 D 解： v1v5v6v2v4v3v2v4v5v6v2v1是含 D所有頂點(diǎn)的一條回路。 14 1 0 x t 0 1 2 ?1 ? 0 1 n 例 3 求下圖 D的強(qiáng)連通分支、單向連通分支。 定義 9 設(shè) D`是 有向圖 D=(V, E)的一個(gè)子圖。如果 D`是強(qiáng)連通的 (單向連通的、弱連通的 ),且 D中不存在真包含 D`的子圖是強(qiáng)連通的 (單向連通的、弱連通的 ),則稱 D`是 D的一個(gè)強(qiáng)連通分支 (單向連通分支、弱連通分支 )。 6 1 3 2 5 4 8 7 9 D 15 1 0 x t 0 1 2 ?1 ? 0 1 n (1) D的強(qiáng)連通分支 ｛ 1｝ ｛ 2, 3, 9, 8, 4, 7｝ 6 1 3 2 5 4 8 7 9 D ｛ 5｝ ｛ 6｝ 上面點(diǎn)集導(dǎo)出的子圖是 D的強(qiáng)連通分支。 3 2 4 8 7 9 1 6 5 16 1 0 x t 0 1 2 ?1 ? 0 1 n (2) D的單向連通分支 D的單向連通分支就是 D本身。 6 1 3 2 5 4 8 7 9 D 注：求 D的強(qiáng)、弱連通分支比較容易，求單向分支比較困難。 定理 2： 有向圖 D=(V,E)的每個(gè)點(diǎn)位于且僅位于 D的某個(gè)強(qiáng) (弱 )連通分支中。 證明：對(duì)于弱連通分支情形，命題結(jié)論是顯然的。 對(duì)于強(qiáng)連通分支情形，因?yàn)椴浑y證明： D中頂點(diǎn)間的強(qiáng)連通關(guān)系是等價(jià)關(guān)系。該等價(jià)關(guān)系對(duì)應(yīng)的等價(jià)類在 D中的導(dǎo)出子圖必然是 D的一個(gè)強(qiáng)分支。而 D的一個(gè)強(qiáng)分支包含的頂點(diǎn)也必然是該等價(jià)關(guān)系的一個(gè)等價(jià)類。 17 1 0 x t 0 1 2 ?1 ? 0 1 n 但是，對(duì)于單向連通分支來(lái)說(shuō)， D的某個(gè)頂點(diǎn)，可能會(huì)分屬于 D的若干個(gè)單向連通分支。原因是單向連通關(guān)系不是等價(jià)關(guān)系。 (三 )、圖的定向問(wèn)題 圖的定向問(wèn)題是有向圖中的一個(gè)典型問(wèn)題之一，具有廣泛的應(yīng)用背景。 城市交通網(wǎng)設(shè)計(jì)問(wèn)題 : 一座城市為某種需要，要把所有街道改為單行道，使得人們?cè)谌我鈨蓚€(gè)位置都可以相互到達(dá)。如何設(shè)計(jì)單行道方向？ 圖論建模：街道交叉口模型為圖的頂點(diǎn)，兩點(diǎn)連線當(dāng)且僅當(dāng)該兩點(diǎn)是某街道的端點(diǎn)。 18 1 0 x t 0 1 2 ?1 ? 0 1 n 問(wèn)題等價(jià)于在模型圖中給出其強(qiáng)連通定向。 對(duì)于任意一個(gè)無(wú)環(huán)圖 G，要對(duì)其作強(qiáng)連通定向，需要解決兩個(gè)問(wèn)題：一是強(qiáng)連通定向的存在性問(wèn)題，二是如何定向問(wèn)題。 上面兩個(gè)問(wèn)題都已經(jīng)得到解決。 存在性問(wèn)題 定理 3 ( 羅賓斯， 1939) 非平凡連通圖 G具有強(qiáng)連通定向當(dāng)且僅當(dāng) G是 2邊連通的。 羅賓斯 (19152023), 美國(guó)拓?fù)鋵W(xué)家，數(shù)理統(tǒng)計(jì)學(xué)家。 強(qiáng)連通定向算法 19 1 0 x t 0 1 2 ?1 ? 0 1 n 強(qiáng)連通定向算法 該算法采用頂點(diǎn)標(biāo)號(hào)方法給邊標(biāo)上方向。設(shè) G=(V, E)是 2邊連通圖。 (1) 在 G中任取頂點(diǎn) w, 令 l (w)=1, L=｛ w｝ ,U=V｛ w
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1