2012-10-02 97 views
2

我有這樣的問題:網絡流程算法

我們給出了一個二部圖。對於例如

A1 B1 
A2 B2 
A3 B3 
A4 

這裏是鄰接表表示(假設圖是雙向)

B1 -> A2, A3 
B2 -> A2, A3, A4 
B3 -> A1 

最終結果應該是在左側的所有節點(AS)具有完全相同1進入邊緣,並在同一時間 - 我們需要最小化需要從單個Bs節點出去的最大邊數。在這種情況下,答案將是:

B3 can connect to A1 
B2 can connect to A2, A4 
B1 can connect to A3 

所以這裏需要的最大邊數出單個BS節點是2。我們不能涵蓋所有作爲,並在同一時間有沒有A B節點2個邊緣從它覆蓋As。

又如:

A1 B1 
A2 B2 
A3 B3 
A4 B4 

B1 -> A1, A2, A3 
B2 -> A1, A2, A3, A4 
B3 -> A1, A2, A3 
B4 -> A1, A2, A3 

在這種情況下,答案將是:

B1 can connect to A1 
B2 can connect to A4 
B3 can connect to A3 
B2 can connect to A2 

這種方式,我們將覆蓋所有的作爲正好一次,並在同一時間,我們已經最小化的最大數量需要走出個人B的邊緣。所以這裏需要出單個BS節點的邊緣的最大數目爲1

又如:

A1 B1 
A2 B2 
A3 B3 
A4 
A5 
A6 

B1 -> A6 
B2 -> A1, A2, A3, A4, A5 
B3 -> 

在這種情況下,答案是5即需要的最大邊數走出去一個單位是5,不能少於這個。

我已經實現了基本的福特fulkerson算法,我知道這也是網絡流量,但不知道如何與它關聯。

如果有人能提供一些有關圖表的提示,那將會很棒。

由於

回答

3

找到一個最佳的解決方案 - 與所有B的具有至多一個出邊緣(如果存在)是簡單的:

  • 添加源和宿的曲線圖。源將有一個出邊 的邊緣,容量爲1的B列表上的所有頂點。
  • 所有(B,A)邊緣的容量爲1.
  • 所有A的邊緣容量都爲1。
  • 現在,運行一個流算法將產生在 頂點的最大數A可以覆蓋有具有各B僅單個 傳出邊緣(最優解,如果存在的話)

編輯:

現在,基於上述想法,因爲你正試圖從一個單個B減少邊緣的最大數目爲A(而不是總人數當中,我預viously認爲),最佳的解決方法很簡單:

while there is no coverage: 
    set capacity(source,b_k) = increase_size() (for each b_k in B) 
    run max flow algorithm on the graph suggested above 
return last flow found 

複雜的O(E*V*#iterations)(在這個問題f <= V,因此,如果福特Fulkerson增是O(EV))的複雜性,其中#iterations可以在最少的最大數量進行線性你尋求,或者使用指數增加,然後在範圍內進行二分搜索(如Evkeny Kluev所建議的),記錄該數字。
由於二分圖E=O(V),我們得到總的O(V^2*log(V))

+0

感謝您的答覆阿米特。這是我的理解 - 在我構建了我的圖(現在忽略二分搜索,我將變成線性:-)) - 假設有三個B,所以源連接到B1,B2和B3。我應該設置源的邊緣容量:B1到1 - 運行最大流量 - 查看有多少As被覆蓋 - 然後設置源的邊緣容量:B2到1 - 運行最大流量 - 查看有多少As被覆蓋然後來源:B3到1然後來源:B1到2來源:B2到2然後來源:B2到2然後來源:B3到2!是對的嗎? – VVV

+0

另外如果我有一個圖表,每個B連接到每個A?在那種情況下,只要我第一次運行最大流量算法,所有的As將被覆蓋。然而,在這種情況下的答案是1,即每個B只需要連接到1A以覆蓋所有的東西!如果我錯過了某些東西,請告訴我。謝謝。 – VVV

+1

@VVV:否,所有邊緣設置爲B的,在第一次迭代之一容量:(源,B1),(源,B2),(源,B3) - 所有設置爲1在第一次迭代。在第二次迭代中,將它們全部設置爲2,並且在第3次到第3次中,...... – amit

2

連接所有A的一個公共匯聚節點與可變容量C邊緣容量1.連接所有B的邊緣到一個公共源極節點。

查找該圖最大的網絡流量,增加C並不是每個A被覆蓋,否則降低。這意味着使用二進制搜索爲C找到最佳值。

+0

感謝Evgeny Kluev爲您的時間!你能解釋一下在這裏增加容量是什麼意思?如果我有一個圖表,其中所有的Bs都連接到所有的As,並且我將C設置爲1表示將源連接到某個B節點的邊,則將覆蓋所有邊。然而,在這種情況下答案是1,因爲每個B需要連接到1 A.答謝。 – VVV

+1

正如你已經從阿米特得到這個解釋,我只會添加一些二進制搜索的細節。對於第一次迭代,您可以將'C'設置爲某個期望值,例如2.然後應用單向二分搜索並像這樣增加'C':2-> 4-> 8-> 16 ... As一旦所有As都被覆蓋,就繼續進行正常的二分搜索:8-> 6-> 5。或者,您可以跳過單向搜索,將「C」設置爲As的數量並執行正常的二進制搜索。 –