正確にパスを増やすのは何ですか？

Question

約computing network flowsを話し、Algorithm Design Manualは言う：

を従来のネットワークフローアルゴリズムは増強経路の考え方に基づいて、繰り返しSからTへの正容量の経路を発見し、フローに追加されています。ネットワークを通るフローは、増強パスを含まない場合に限り最適であることが示される。

augmenting pathsはわかりません。私はGoogleで検索し、発見した：

• Augmenting Path in Wolfram

• Flow network in Wiki

彼ら上記の引用のすべての参照。

augmenting pathは本当にはっきりと説明できますか？

Answer 1

補強パスは、単純なパス（サイクルを含まないパス）です。ソースからシンクまでの容量が正のエッジのみを使用してグラフを作成します。

上記のステートメントは何らかの形で明らかです。ソースからシンクまでのパスが見つからない場合は、容量を増やすことはできません。

ところで、その声明の証明はそれほど簡単ではありません。

Answer 2

拡大表示は、増加メイクを大きくすることを意味します。所与のフローネットワークG=(V,E)およびフローfでは、増補パスpは、残余ネットワークGfのsource sからsink tへの単純なパスです。 residual networkの定義により、増強パスのエッジ(u,v)上のフローを、(u,v)と(v,u)のいずれかが元のフローネットワークGのいずれかに制約違反なしに、容量Cf(u,v)まで増加させることができます。 また、拡張パスp内の各エッジのフローを増やすことができる最大量をresidual capacity of pと呼びます。 証明は、thomas hによるアルゴリズムの紹介にあります。 cormenなど...

Answer 3

ソースからシンクまでの経路をどのようにして確認できますか？ BFSの修正バージョンを使用しています。シンクに達するまではソースからBFSを行い、残りの容量（つまり、そのエッジの最大容量 - 現在のフロー> 0）がある場合にのみエッジをトラバースします。また、ソースからシンクまでのこのパスでは、そのパスを通過できる最大フローである最小残存容量を維持します。

bool maxFlowAchieved = false; 
int maxFlow = 0; // keeps track of what is the max flow in the network 
while(!maxFlowAchieved) 
{ 
    //BFS returns collection of Edges in the traversal order from source to sink 
    std::vector<Edge*> path = BFS(source, sink); 
    maxFlowAchieved = path.size() == 0; // all paths exhausted 
    if(maxFlowAchieved) 
     break; 
    // traverse each edge in the path and find minimum residual capacity 
    // edge->residual = edge->maxCapacity - edge->currentflow 
    int allowedFlow = GetMinResidualOnPath(path); 
    // Now add additional flow to each edge in the path. 
    // i.e. for each edge in path, edge->currentflow += allowedFlow 
    // clearly, edge->currentflow + allowedFlow <= edge->maxCapacity 
    SaturatePath(path, allowedFlow); 
    maxFlow += allowedFlow; 
} 

return maxFlow; 

Answer 4

ソースからシンクまで繰り返してシークェンスを見つけるプロセスです。たとえばFord-Fulkersonアルゴリズムの場合、最初はすべてのエッジ上のすべてのフローがゼロになります。反復処理では、すべてのパス/エッジの値を取って、拡張パスと呼ばれるフローを見つけます。