network-flow

0熱度

1回答

我正在研究算法的分析。我目前正在閱讀Network Flow算法。我正在考慮應用Network Flow算法有關尋找最低成本bipartite matchings。讓G與相應的網絡流量G' 讓M是在G perfect matching讓G<sub>M</sub>與此匹配從喬恩·克萊因伯格和伊娃·塔爾多斯Algorithm Design 7.13相關的residual graph第406頁， T

2熱度

1回答

是否有算法在無向圖分離源和接收器中查找最小切割

我有一個邊緣加權無向圖和2個節點（通常稱爲源和接收器）。我需要找到一組最小可能重量的邊，將這2個節點分成2個弱分量。我知道關於Ford-Fulkerson's maximum flow algorithm和他有關有向圖上的maximum flow and minimum cut relation的定理。我也知道福特 - 福克森最大流算法對無向圖的修改，它用兩個相反的有向邊替換每個無向邊，並同時

3熱度

1回答

Ford-Fulkerson算法可以找到哪種最小切分？

網絡中可能有多個分割點。 E.g：具有四個分切口和福特富爾克森找到一個「更接近」於S（源極）。我們可以對所有網絡說同樣的話嗎？那就是說，福特 - 福克斯森發現最接近消息來源的裁員？如果屬實，我們如何正式確定流量網絡中「最接近源頭」的概念？

0熱度

1回答

如何將多圖解簡化爲簡單有向圖

假設存在一個網絡有多條邊，對於任意一對頂點（u，v），圖中包含了從u到v和從v到u的幾個有向邊，每個有邊自己的能力和重量。如何將這個多圖減少爲一個簡單的有向圖，在u和v之間只有一條邊？注意：不確定這種方法是否正確，我將u和v之間的各個邊的能力和權重相加，並將它們合併到一個從u到v的超邊，以及從v到u的一個邊。但是，我如何進一步將這兩者合併爲u和v之間的一條邊，以及它指向哪個方向？

0熱度

1回答

最小費用流積分定理

最小費用流問題的完整性定理指出，給定「積分數據」，對於與最小費用流相對應的問題，總是有一個整體解決方案。整體數據的概念對我來說有點混亂，因爲大多數論文和教程都指出，需求，供應和能力應該是不可或缺的。現在，一個容量約束通常被表示爲 l_i <= c_i <= u_i 其中l_i是下界邊緣i的容量，並且u_i是上限。爲了保持完整性定理，l_i and u_i是不是整數？這個疑問來自這樣的事實，這並

0熱度

1回答

使用graphviz創建tcp流程圖？

是否graphviz的還是它的子項目支持TCP流型圖，e.g：我已經通過了graphviz的文件和畫廊看，但沒有跳出我。

2熱度

1回答

改進Dinic算法的動態樹數據結構

我想將Dinic算法與動態樹一起應用。但我發現很少的消息來源。特別是關於動態樹。如果有詳細的解釋或使用動態樹的一些簡單的源代碼的好源，這將是非常好的。任何人遇到類似的東西？在此先感謝

-2熱度

1回答

網絡流量：對或錯

In a directed graph with at most one edge between each pair of vertices, if we replace each directed edge by an undirected edge, the maximum flow value remains unchanged. 爲什麼它是假的？爲什麼以及如何改變流量？謝謝。

2熱度

1回答

具有單位容量邊緣的流動網絡中的Ford-Fulkerson方法的時間複雜度

Ford-Fulkerson算法是否可以找到單位容量流網絡（所有邊都具有單位容量）的最大流量，其中n頂點和m邊O(mn)時間？

1熱度

1回答

爲什麼CVXOPT爲這種非線性網絡流量優化提供排名誤差？

我正在考慮使用cvxopt來解決一些非線性網絡流量優化問題。爲了理解基礎知識，我用一個非常簡單的測試網絡來測試它，只有4個頂點和5個邊。我的網絡看起來像this。藍色和紅色節點分別是源和匯。在每個邊緣上的成本是： alpha*x**2 x表示包含在每個邊緣上的流動的矢量，和α是一些係數。我的優化問題是： min sum(alpha*x**2) subject to: E*