網絡流量中的流通

Question

我正在閱讀Robert Sedwick編寫的算法書。

注意：「s」是源代碼，「t」是坦克。

Augument任何流網絡與來自「T」，以「s」用流量和 容量等於網絡的值的邊緣，並且知道流入等於 到流出對augumented網絡中的任何節點集。這樣的流程被稱爲循環，並且這種構造表明最大流問題降低爲尋找循環的問題，該循環使沿給定邊的流最大化。

給定一組週期和每個週期的流量值，很容易通過跟隨每個週期 並將指示的流量添加到每個邊沿來計算相應的循環。相反的屬性是 更令人驚訝;我們可以找到一組循環（每個循環的流量值爲 ），與任何給定的循環相當。沿着一組最E階定向循環，任何循環都可以表示爲流程 。

我上面的解釋問題

1. 請求用例子來解釋什麼作者的意思是，我們如何能減少「maxflow問題簡化爲找到一個循環 沿着一個最大化流的問題給予優勢。「？

2. 可以用下面的段落簡單的例子來解釋。

「給定一組的週期和每個循環的流量值，很容易 通過每個循環 以下以及將所述指示流動到每個邊緣計算相應的循環，相反的性質是 更令人驚訝;我們可以找到一組週期（每個流量值爲 ），這相當於任何給定的循環。「

謝謝！

Answer 1

1. 如果你有源S和匯噸maxflow問題，你可以在這個問題只需添加一個邊緣的T>取值轉換成最大流通問題。從s到t的原始最大流量現在轉換成最大循環s→t→s。

2. 如果您有一個循環列表（圖中的閉合路徑），並且每個循環都與流量N相關聯，則可以遍歷所有循環並將流量值N添加到循環所經過的邊界。以這種方式，圖中的每條邊都會有一個爲其計算的流量值，這就是圖中的總流通量。相反，該定理說，只要你在總圖中有一個循環，它就可以分解成循環。這裏是一個最大循環的一個例子，在每個邊緣上的符號A（B）表示該流是與邊緣的最大容量爲b：

   3(3)  2(2) 
   a ----> b -----> c 
   ^  |1(1) | 
   |3(3) V  V 2(4) 
   d<------e<-------f 
       3(4)  2(3) 
   

相應週期是：abeda與流量值1，並且流量值2超過。這兩個循環一起定義瞭如上所示的最大循環。