我有這樣的問題:網絡流程算法
我們給出了一個二部圖。對於例如
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算法,我知道這也是網絡流量,但不知道如何與它關聯。
如果有人能提供一些有關圖表的提示,那將會很棒。
由於
感謝您的答覆阿米特。這是我的理解 - 在我構建了我的圖(現在忽略二分搜索,我將變成線性:-)) - 假設有三個B,所以源連接到B1,B2和B3。我應該設置源的邊緣容量:B1到1 - 運行最大流量 - 查看有多少As被覆蓋 - 然後設置源的邊緣容量:B2到1 - 運行最大流量 - 查看有多少As被覆蓋然後來源:B3到1然後來源:B1到2來源:B2到2然後來源:B2到2然後來源:B3到2!是對的嗎? – VVV
另外如果我有一個圖表,每個B連接到每個A?在那種情況下,只要我第一次運行最大流量算法,所有的As將被覆蓋。然而,在這種情況下的答案是1,即每個B只需要連接到1A以覆蓋所有的東西!如果我錯過了某些東西,請告訴我。謝謝。 – VVV
@VVV:否,所有邊緣設置爲B的,在第一次迭代之一容量:(源,B1),(源,B2),(源,B3) - 所有設置爲1在第一次迭代。在第二次迭代中,將它們全部設置爲2,並且在第3次到第3次中,...... – amit