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