第11章 網路流.

Presentation on theme: "第11章 網路流."— Presentation transcript:

1 第11章 網路流

2 本章學習重點 最大流量問題 配對問題

3 摘要 網路流量 最大流量問題 Ford-Fulkerson法 Edmonds-Karp演算法 配對問題

4 網路流量 有向加權圖經常應用在網路流量相關的問題。最大 流量問題是關於網路流量最簡單的題目。如何有效 地最佳化網路流量仍是目前相當熱門的研究題目。

5 流量網路 流量網路的邊線上均有容量的限制，容量值原則上 大於零，相當於權值的定義。通常容量值為0的話， 即代表X和Y間並不相連。
在網路流量圖形中，通常會定義兩個節點：源點和 匯點。最大流量問題就是指從源點到匯點之間的最 大流量。

6 剩餘流量網路 如果將邊線上的容量值減去目前的流量值，我們可 以得到該網路的剩餘流量網路，表示任意兩個節點 之間還能夠容納的流量。

7 遞增路徑 在剩餘流量網路中，存在一條路徑可以遞增S到T 的總流量，我們將這條路徑稱為遞增路徑。
一條遞增路徑真正可貢獻的流量，會受限於途中最 小容量的邊線。

8 最大流量即最小切線容量 流量網路中的切線將所有節點分成兩部分，一半包 含源點，另一半包含匯點。每一條切線上的淨流量 值都會是相等的。
切線的容量定義為所有順向流量（從源點這半部流 向匯點那半部）都是最大的時候。 既然每一條切線上的淨流量值都是相等的，那麼只 要找出所有可能的切線，其最小的切線容量值，理 論上應該會等於此流量網路的最大流量值。這個就 是著名的「最大流量即最小切線容量」定理。

9 Ford-Fulkerson法 他們計算兩點之間最大網路流量的方法其實是沿用 剩餘流量網路和遞增路徑的觀念：首先一開始先將 所有路徑上的流量設為0。然後，嘗試在剩餘網路上 尋找任意遞增路徑。只要存在一條遞增路徑，就沿 著路徑增加邊線上的流量。持續重複這個流程，直 到沒有遞增路徑為止。

10 Ford-Fulkerson法範例 使用深度優先搜尋法 來選擇遞增路徑。

11 Ford-Fulkerson法範例… 這時候乍看網路流量似乎已經沒有成長空間。可是從其剩 餘流量網路G”卻可以找出{A, C, D, B, E, F}路徑，繼續貢獻1 單位流量。

12 Edmonds-Karp演算法 任意選擇遞增路徑有可能白做許多工:

13 配對問題 所謂的配對是指在一個圖形中，不共用節點 的邊線集合。亦即任意兩條邊線XY和UV，其 四個節點均不相同。
最大配對則是指邊線數目最多的配對集合。 特別是二分圖形的配對問題更是經常被拿來 討論。

14 配對問題與流量問題 要解決二分圖形的配對問題，我們可以在兩邊分別加上源 點和匯點。並且設定所有邊線的容量為1。如此一來，最大 配對問題就可以轉換成最大流量問題。

15 結論 本章節介紹了流量網路的概念，並且導入計算流量 網路的三個重要元素：剩餘流量網路，遞增路徑， 和切線。
我們利用了一點技巧將配對問題轉換成為流量問題。 這種情形經常發生在演算法的世界裡。這帶給我們 的啟發是，從另一個角度去思考問題的本質，有時 候會發現新的世界。