network-flow

2熱度

1回答

計算面向圖中不同s-t切割的數量

我正試圖在面向未加權圖形中查找不同s-t切割的數量。在文章Enumeration in Graphs p。 45我找到了如何列舉這些削減的好方法（第7.3節）。如果我只對這些切割的數量感興趣，並且我實際上不需要枚舉它，是否可以使用更快或更簡單的算法？ 我正在使用的s-t切割的定義如下。我們有一個有向圖，其中兩個頂點標記爲S和T。 Cut是一個圖的邊的一組邊，從而通過去除這些邊將不再存在從頂點S到頂

algorithm graph-algorithm network-flow 2011-12-01

---

-2熱度

1回答

在二分圖中的最大匹配

我在二分圖問題中遇到最大匹配。問題是這樣的： 給定一個有m個圓孔的板，並給出一組n個圓盤。孔編號爲h ，...，h m，以及作爲d的圓盤，...，d n。 我們有一個m行n列的矩陣A. A [i] [j] = 1如果h 我可以適合d Ĵ（即，h的我 ≥直徑d Ĵ的直徑），否則爲0。 考慮到任何一個孔最多隻能包含一個圓盤的情況，我需要找到孔配合最大的配置。 我讀過這個問題可以模擬到網絡流量問題，但不

c algorithm matching bipartite network-flow 2011-08-29

---

0熱度

1回答

如果所有路徑具有相同的長度，如何啓動Edmonds-Karp實現？

如果所有路徑長度相同，如何選擇Edmonds-Karp algorithm的起始路徑？在這種情況下，最大流量根據路徑順序決定而改變。

c++ algorithm network-flow edmonds-karp 2011-12-29

---