10

Cormen の「Introduction to algorithms 2nd Edition」から Ford-Fulkerson アルゴリズムを勉強しています。これは、有向グラフ G=(V, E) の擬似コードで次のように記述されます。ここで、f は VxV で定義されたフローです。

FORD-FULKERSON(G, s, t)
    for each edge (u,v) in E(G)
        do f[u, v] = 0
           f[v, u] = 0
    while there is a path p from s to t in the residual network Gf
        do m = min{c(u, v)-f[u, v]: (u, v) is on p}
            for each edge (u, v) on p
                do f[u, v] = f[u, v] + m
                   f[v, u] = - f[u, v]

残差グラフ Gf は G と同じ頂点を持ち、c(u, v) - f(u, v) > 0 である順序付けられた頂点のペア (u, v) をエッジとして持ちます (編集: c は容量関数です)。開始時に与えられ、グラフの一部ではないエッジでゼロになるように拡張されます)

「両方向」にエッジが存在する場合、たとえばエッジとその逆がグラフにある場合にアルゴリズムで何が起こるかはわかりません。最小値の c(u, v) は、グラフの元の容量に対するものであると想定しています。(a, b) と (b, a) の両方がエッジである場合、残差グラフの 4 つのエッジを処理する必要がありますか? 現時点では、平行エッジを直接処理することはできません。

SO に関する次の質問を見つけました: 最大フロー - フォード ファルカーソン: 無向グラフ しかし、結果がどうなるかはわかりません。

4

1 に答える 1

5

疑似コードのどこにも、グラフが循環的であるか「逆エッジ」があるかについての仮定はありません。エッジがあるだけです。

「両方向」にエッジがある場合、c(u,v) と c(v,u) は区別されます。c(u,v) は u から v へのエッジの容量であり、c(v,u) は v から u へのエッジの容量です。それらは、他のエッジとの関係と同じように、互いに関係を持ちません。

別の言い方をすれば、 c(u,v) と f[u,v] は両方とも、実際にはverticesではなく、 edgesの関数です。(そして、そのように書かれた場合、アルゴリズムはより明確になると思います。) したがって、それらを c(E) および f[E] と考えてください。ここで、E はエッジです。「残差ネットワーク」も、頂点ではなくエッジの集合です。残差ネットワークは、c(E) - f[E] が正であるすべてのエッジです。

アルゴリズムが行うのは、ソースからターゲットへのパスのうちまだ予備の容量があるものを見つけ、その予備の容量を消費するようにフローを増やすことだけです。f[E] はエッジを横切るフローです。したがって、すべての f[E] が c(E) より小さい s から t へのパスを見つけ、そのパスに沿って最小の差を取り、そのパスに沿ってフローをその差だけ増やします。空き容量のあるパスがなくなるまで繰り返します。

E と E' が互いに反転する 2 つのエッジである場合、アルゴリズムは気にしません。それらを独立したエッジとして扱います。

アルゴリズムの機能を理解するのは簡単です。収束することを証明すること、正しい答えが得られることを証明すること、実行時間を分析することは難しい部分です。

[アップデート]

ああ、なるほど; f[u,v] は実際には u から v への流れであり、辺に沿った流れではありません (反対方向に u と v を接続する 2 つの辺が存在する可能性があるため)。

頂点に基づいて f[u,v] を維持できると思いますが、コスト グラフと残差グラフはエッジに基づいている必要があります。したがって、基本的にアルゴリズムが言うことを正確に実行します。パス上の各エッジ E = (u,v) について、c(u,v)-f[u,v] の最小値を見つけ、それに応じて f[] 値を更新します。次に、元のグラフのエッジに基づいて新しい残差グラフを計算します。つまり、各エッジ E = (u,v) について、c(u,v) が f[u,v] より大きい場合、E は残差グラフのメンバーです。

于 2011-10-12T15:37:10.940 に答える