查找任何網絡的最大流量由給定的算法

Question

你能幫助我有以下問題？：

假設我們有一個算法來解決流量網絡中每個節點的出度是最大流量的問題最多2. 我需要展示如何使用這種算法來解決任何網絡中的最大流量問題。

如果這是一個重複，那麼請將我重定向到相關答案。

謝謝所有

Answer 1

它確實有可能變換曲線以這樣的方式，每個節點的出度至多爲2，並在轉化的曲線圖中的最大流量是等於最大流量在最初的圖中。

下面描述了一種這樣的轉換。假設我們有一個節點的出度大於2.那麼我們可以添加儘可能多的中間節點作爲該節點的出度，並按照下圖所示的方式連接它們。

無限容量的邊緣確保我們可以開始發送相同的流量從A到任何的後繼者。從X節點到B節點的邊緣確保我們不能發送大於最初可能的流量。

通過對出度大於2的每個節點重複此轉換，我們獲得一個圖，其中每個節點的出度最大爲2，其最大流量等於初始圖的最大流量。