1

私は有向グラフを持っています

グラフ

まず、Ford-Fulkerson のアルゴリズムを使用して、ネットワークの流れを増やしました。頂点をマークすると、path: のフローがs->a->b->d->t1 つ増えることがわかったので、グラフは次のように変更されました。

FF使用後のグラフ

最大フローを検索するときは、グラフの最小カットと外側部分を接続するエッジのすべての容量を合計する必要があることを知っています。私の最小限のカットには vertices: が含まれs, a, cているため、取得したすべてのエッジを合計すると、これは 5 であるc(G, !G) = 3 + 2 +2 + 1フローよりもはるかに大きくなります。t

私は何を間違っていますか、FFまたは最小限のカットを台無しにしましたか?

4

1 に答える 1

1

ミニマムカットではありませんs, a, cがs, a, b, c。その容量は5、計算した最大フローです。

残差ネットワークの定義を使用して最小カットを見つけることができます。sFord-Fulkerson は、残余ネットワーク間および残余ネットワーク内にパスがない場合に終了することを思い出してくださいt。

最小カット(S,T)は次のように定義されます。

S = { v | there exists a path from s to v in the residual network }

あなたのグラフでは、フローが weightであるため、残りのネットワークbからノードに到達できます。cb->c3

于 2015-06-20T16:17:04.257 に答える