26 最大流

就像我們可以對一個路網構建一個有向圖求最短路一樣,我們也可以將一個有向圖看成是一個"流量網絡(flow network)",用它來回答關于流的問題.

? ? Just as we can model a road map as a directed graph in order to find the shortest?path from one point to another, we can also interpret a directed graph as a “flow?network” and use it to answer questions about material flows.

想像一下在一個流量系統中,一種物質從一個源點,那個物質產生的地方,流向一個匯點,也就是物質流向的地方.源點以一個固定的速率產生那種物質,匯點以相同的速度消耗那種物質.

? ? The source produces the material at some steady?rate, and the sink consumes the material at the same rate.

在這個流量系統的每一個點上,這種物質的流速(flow)顧名思義,就是這種物質移動地多快.流量網絡可以為許多問題建立模型,包括流經管道的液體的速度,流水線的組裝,流經電路的電流,以及信息穿過聯絡網絡.

? ? The “flow” of the material at any point in the system is intuitively the rate at which the material moves.Flow networks can model many problems, including liquids flowing through pipes,parts through assembly lines, current through electrical networks, and information
through communication networks.

可以想像,我們的流量網絡的每一條邊(edge),都對物質流動有一個限制.每一個限制都給出了一個額定流量(stated capacity),也就是這種物質可以流經這條邊的最大速度,比如每小時有200加侖液體可以流經一個管道或一條電線可以通過20安培的電流.頂點(vertex/vertices(復數))是限制連接的地方,除非是源點或者匯點,流經這些頂點的流是不會改變的.換句話說,流入一個頂點的流等于流出一個頂點的流.我們將這個性質稱為流量保護(flow conservation),這與在此流量網絡是一個電路時,應用在這個電路上的基爾霍夫電壓定律是等價的.

?

? ? We can think of each directed edge in a flow network as a conduit for the material. Each conduit has a stated capacity, given as a maximum rate at which the material can flow through the conduit, such as 200 gallons of liquid per hour through?a pipe or 20 amperes of electrical current through a wire. Vertices are conduit?junctions, and other than the source and sink, material flows through the vertices?without collecting in them. In other words, the rate at which material enters a vertex must equal the rate at which it leaves the vertex. We call this property “flow?conservation,” and it is equivalent to Kirchhoff’s current law when the material is?electrical current.

在最大流問題中,我們將要計算的,是從源點到匯點不觸犯這個網絡中任何限制的最大流量.這是對于流量網絡最簡單的應用.正如我們將在這章中看到的,這個問題可以通過一些十分有效率的算法來解決.更進一步的說,我們將用這些基礎的網絡流算法來解決一些更加復雜的網絡流問題.

?

這個章節將要敘述兩種不同的解決最大流問題的算法.#26.1將網絡流問題中可能用到的記號和這個問題本身形式化了.#26.2描述了傳統的FFF(Ford and Fulkerson for Finding maximum flows)算法.這種算法的一個應用,就是尋找一個二分無向圖的最大匹配,將在#26.3中出現.#26.4呈現了pr(push relabel)算法,是構成當今最快的幾種最大流算法的基礎.#26.5則描述了rtf(relabel-to-front)算法,是一種prpr算法的特殊實現,可以在O(V³)的時間內跑出來.雖然這不是已知最快的算法,它勾勒了一些漸進意義上最快的算法的一些技巧,而且在實際使用中,rtf是足夠快的.

[先更新這些吧..//亮點自尋]

轉載于:https://www.cnblogs.com/tmzbot/p/4160739.html

總結

以上是生活随笔為你收集整理的[另开新坑] 算导v3 #26 最大流 翻译的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。