Posted on 2011-04-05 16:23
Mato_No1 閱讀(3096)
評(píng)論(0) 編輯 收藏 引用 所屬分類:
網(wǎng)絡(luò)流
圖的連通度問題是指：在圖中刪去部分元素（點(diǎn)或邊），使得圖中指定的兩個(gè)點(diǎn)s和t不連通（不存在從s到t的路徑），求至少要?jiǎng)h去幾個(gè)元素。
圖的連通度分為點(diǎn)連通度和邊連通度：
（1）點(diǎn)連通度：只許刪點(diǎn)，求至少要?jiǎng)h掉幾個(gè)點(diǎn)（當(dāng)然，s和t不能刪去，這里保證原圖中至少有三個(gè)點(diǎn)）；
（2）邊連通度：只許刪邊，求至少要?jiǎng)h掉幾條邊。
并且，有向圖和無(wú)向圖的連通度求法不同，因此還要分開考慮（對(duì)于混合圖，只需將其中所有的無(wú)向邊按照無(wú)向圖的辦法處理、有向邊按照有向圖的辦法處理即可）。
【1】有向圖的邊連通度：
這個(gè)其實(shí)就是最小割問題。以s為源點(diǎn)，t為匯點(diǎn)建立網(wǎng)絡(luò)，原圖中的每條邊在網(wǎng)絡(luò)中仍存在，容量為1，求該網(wǎng)絡(luò)的最小割（也就是最大流）的值即為原圖的邊連通度。
【2】有向圖的點(diǎn)連通度：
需要拆點(diǎn)。建立一個(gè)網(wǎng)絡(luò)，原圖中的每個(gè)點(diǎn)i在網(wǎng)絡(luò)中拆成i'與i''，有一條邊<i', i''>，容量為1（<s', s''>和<t', t''>例外，容量為正無(wú)窮）。原圖中的每條邊<i, j>在網(wǎng)絡(luò)中為邊<i'', j'>，容量為正無(wú)窮。以s'為源點(diǎn)、t''為匯點(diǎn)求最大流，最大流的值即為原圖的點(diǎn)連通度。
說(shuō)明：最大流對(duì)應(yīng)的是最小割。顯然，容量為正無(wú)窮的邊不可能通過(guò)最小割，也就是原圖中的邊和s、t兩個(gè)點(diǎn)不能刪去；若邊<i, i''>通過(guò)最小割，則表示將原圖中的點(diǎn)i刪去。
【3】無(wú)向圖的邊連通度：
將圖中的每條邊(i, j)拆成<i, j>和<j, i>兩條邊，再按照有向圖的辦法（【1】）處理；
【4】無(wú)向圖的點(diǎn)連通度：
將圖中的每條邊(i, j)拆成<i, j>和<j, i>兩條邊，再按照有向圖的辦法（【2】）處理。