第11章 網路流
本章學習重點 最大流量問題 配對問題
摘要 網路流量 最大流量問題 Ford-Fulkerson法 Edmonds-Karp演算法 配對問題
網路流量 有向加權圖經常應用在網路流量相關的問題。最大 流量問題是關於網路流量最簡單的題目。如何有效 地最佳化網路流量仍是目前相當熱門的研究題目。
流量網路 流量網路的邊線上均有容量的限制，容量值原則上 大於零，相當於權值的定義。通常容量值為0的話， 即代表X和Y間並不相連。 在網路流量圖形中，通常會定義兩個節點：源點和 匯點。最大流量問題就是指從源點到匯點之間的最 大流量。
剩餘流量網路 如果將邊線上的容量值減去目前的流量值，我們可 以得到該網路的剩餘流量網路，表示任意兩個節點 之間還能夠容納的流量。
遞增路徑 在剩餘流量網路中，存在一條路徑可以遞增S到T 的總流量，我們將這條路徑稱為遞增路徑。 一條遞增路徑真正可貢獻的流量，會受限於途中最 小容量的邊線。
最大流量即最小切線容量 流量網路中的切線將所有節點分成兩部分，一半包 含源點，另一半包含匯點。每一條切線上的淨流量 值都會是相等的。 切線的容量定義為所有順向流量（從源點這半部流 向匯點那半部）都是最大的時候。 既然每一條切線上的淨流量值都是相等的，那麼只 要找出所有可能的切線，其最小的切線容量值，理 論上應該會等於此流量網路的最大流量值。這個就 是著名的「最大流量即最小切線容量」定理。
Ford-Fulkerson法 他們計算兩點之間最大網路流量的方法其實是沿用 剩餘流量網路和遞增路徑的觀念：首先一開始先將 所有路徑上的流量設為0。然後，嘗試在剩餘網路上 尋找任意遞增路徑。只要存在一條遞增路徑，就沿 著路徑增加邊線上的流量。持續重複這個流程，直 到沒有遞增路徑為止。
Ford-Fulkerson法範例 使用深度優先搜尋法 來選擇遞增路徑。
Ford-Fulkerson法範例… 這時候乍看網路流量似乎已經沒有成長空間。可是從其剩 餘流量網路G”卻可以找出{A, C, D, B, E, F}路徑，繼續貢獻1 單位流量。
Edmonds-Karp演算法 任意選擇遞增路徑有可能白做許多工:
配對問題 所謂的配對是指在一個圖形中，不共用節點 的邊線集合。亦即任意兩條邊線XY和UV，其 四個節點均不相同。 最大配對則是指邊線數目最多的配對集合。 特別是二分圖形的配對問題更是經常被拿來 討論。
配對問題與流量問題 要解決二分圖形的配對問題，我們可以在兩邊分別加上源 點和匯點。並且設定所有邊線的容量為1。如此一來，最大 配對問題就可以轉換成最大流量問題。
結論 本章節介紹了流量網路的概念，並且導入計算流量 網路的三個重要元素：剩餘流量網路，遞增路徑， 和切線。 我們利用了一點技巧將配對問題轉換成為流量問題。 這種情形經常發生在演算法的世界裡。這帶給我們 的啟發是，從另一個角度去思考問題的本質，有時 候會發現新的世界。