問題タブ [max-flow]

opencvには max-flow アルゴリズム (GCGRAPHファイル gcgraph.hpp のクラス) が実装されています。こちらから入手できます。

このクラスによって実装されている特定の max-flow アルゴリズムを知っている人はいますか?

これは試験準備の一部です。max-flowアルゴリズムと関係があることは知っていますが、ヒントをいただければ幸いです：

G=(V,E)無向連結グラフと、w:E->R重み関数、eエッジ、および を考えk > 0ます。新しいグラフの最小全域木に属するkように、グラフから多くてもエッジを削除できるかどうかを判断するアルゴリズムを説明してください。e

スパニング ツリーは一種の完璧なマッチングだと思います。しかし、e と適切な量の他のエッジを含む最小限にするにはどうすればよいでしょうか?

max-flow と min-cut の間の有名な二重性が実際に無限の値の容量を許容するかどうか疑問に思っています。これはそうではないように見える簡単な例です：

ソース s、シンク t、その他 5 つのノード a、b、c、d、e

s -> a: 容量 3

s -> b: 3

a -> c: \infty

a -> d: \infty

b -> d: \infty

b -> e: \infty

c -> t: 1

d -> t: 1

e -> t: 4

最大フローは 5 です。ただし、容量が 5 のカットはありません。これは、容量が無限であるため、a、b、c、d、e のすべてがカットの同じセット/半分に属さなければならないためです (そうでない場合は、カット セットの \infty 重量)。

トップコーダー サイトからプッシュ再ラベル アルゴリズムを学習していました: http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=maxflowPushRelabel 実装に何か問題があると思います。ノードが飽和したときに、ノードはどのようにして過剰なフローをノードに押し戻すことができますか。例えば：

1 から 3 までの最大フローを見つけながら、ある段階でフローを 2 から 1 に戻す必要があります (2 には出力エッジがないため)。しかし、先入れ先出しアルゴリズムのコード実装では、16行目のループが から実行され0 to G[u].size()ます。2 には 2 から 1 へのエッジがないため、フローを 1 に戻すにはどうすればよいでしょうか?

必要に応じて、私のくだらない実装を次に示します。

C1 都市はいくつかの商品を喜んで販売し、他の C2 都市はいくつかの商品を喜んで購入します (各都市は商品を販売または購入できますが、両方を行うことはできません)。各販売都市はその商品を 1 つの都市にのみ販売し、各購入都市は 1 つの都市からのみ商品を購入します。

あなたの目標は、交換される商品の量が最大になるように利己的な都市を接続することです。

難しいのは、各都市が 1 つの都市に対してのみ商品を売買できるという制限です。

反例を見つけようとしていますが、存在しないようです。しかし、証拠も見つかりませんでした。多分誰かが何か考えを持っていますか？詳細は次のとおりです。

ゼロ以外の最大フロー値を持つすべての st フロー ネットワークには、そのエッジの容量を減らすと最大フローの値が減少するようなエッジが存在します。これは真か偽か？