資源收藏分享
博觀而約取,厚積而薄發
一個由多個站點連接而成的網絡裡,每對站點之間都有一定的數據傳輸限制 (單向)。現在你需要計算從網絡的入口(
\(s\) )到出口( \(t\)
)之間,數據可以同時傳輸的最大速度是多少。
如下圖,從 \(s\) 到 \(t\)
的最大傳輸速度為 2,最大速度會被路徑上最大傳輸流量所限制,因爲從 \(s\) 到 \(t\) 勢必通過路線 \(v1\rightarrow v2\)
,故這張圖的最大流量為 2。
flowchart LR
s --10--> v1 --2--> v3 --13--> v4 --11--> t
而下面這個圖的最大流量為 19,下文提供一種可能的傳輸方式:
flowchart LR
s --10--> v1
s --17--> v2
v1 --7--> v3 --11--> t
v2 --9--> v4 --16--> t
v1 --6--> v4
上述這樣的圖叫做 Network
Flow (網路流),在這樣的圖上尋找這種最大流
的想法還可以運用在最小割
(後文會再解釋)、最多不重複路徑
、二分圖最大匹配
、二分圖最小頂點覆蓋
等圖論問題。