關於網絡流量均衡屬性

Question

我正在閱讀有關圖形算法的Robert Sedwicks書中的網絡流算法。以下是該書的文本片段。

性質：任何st流都具有流出s的屬性等於 流入t。

證明：Augument與邊緣網絡從虛設頂點爲s， 與流和容量等於從「S」中流出，並與邊緣 從「T」到另一虛設頂點，具有流量和容量等於流入「t」的 。然後，我們可以通過 歸納證明一個更一般的屬性：入口等於任何一組頂點的流出（不包括包含虛擬頂點的 ）。

這個屬性對任何單個頂點都是真實的，通過局部平衡。 現在，假設對於給定的一組頂點「S」它是對的，並且我們添加單個頂點「v」來使集合S1 = S U {v}。爲了計算S1的流入和流出，注意S中從「v」到某頂點 的每條邊減少流出（從V）減少與減少流入 （到S）相同的量;從S中的某個頂點到v的每個邊減少流入（到v）與減少流出（從S）相同的量;並且所有其他邊緣 爲S1提供流入或流出當且僅當它們爲S或v時這樣做 因此，流入和流出對於S1是相等的，並且流量 的值等於v和S的流量減去在邊緣上的流量連接到S中的頂點（方向爲 方向）之和。

應用這個屬性來設置所有的網絡頂點，我們 發現，從其關聯的虛擬頂點源的流入是 等於匯的流出assicated虛擬頂點山雀。

我對以上的證明問題：

1. 什麼是筆者的「從各個邊緣‘V’，以S中一些頂點減少相同量流出（從V），因爲它減少意味着流入（對S）「？ 可以用任何一個簡單的例子來解釋。

2. 作者的意思是「從S中的某個頂點到v的每個邊減少流入量（到v）相同的量，因爲它減少流出量（從S）;所有其他邊爲S1提供流入或流出當且僅當他們這樣做S或V「？請用簡單的例子來解釋。

3. 作者的意思是「流入和流出對於S1是相等的，而流 的值等於v和S的流的值減去邊緣上的流的總和connectin v到S中的頂點（任一方向）。「 ？請用例子來解釋。

謝謝！

Answer 1

該段落寫得不是很好，但如果我把它寫得很對，作者意味着從v到S頂點的流（名爲this vertex t）會增加從給定值到v的流出量，但它也是以相同的值增加t的流入量。因此，添加這樣一個優勢，我們仍然認爲總和流入等於總和流出量。類似地，對於從S到V的頂點的邊，我們增加v的流入和S中頂點的流出具有相同的值。所有其他邊緣連接來自S的兩個頂點，並且通過歸納假設，它們的總和流入等於它們的總和流出。請注意，而不是術語減少頂點v的流出，我用「增加流出量」，因爲它對我來說似乎更自然。 我不敢猜測作者第二到最後一段的最後一句是什麼意思。

希望至少有一點幫助。

我相信有一些書籍，這個特定的定理似乎更好地解釋了例如Thomas H. Cormen，Charles E. Leiserson，Ronald L. Rivest，Clifford Stein所寫的「算法導論」。