問題タブ [network-flow]

Ford-Fulkerson アルゴリズムは、単位容量フロー ネットワーク (すべてのエッジに単位容量がある) の最大フローを、時間内にn頂点とmエッジで見つけますO(mn)か?

色付きの有向グラフ (各ノードには色があります) があり、ノード A からノード B へのパスが存在し、そのパスが各色を MOST で 1 回通過するかどうかを調べたいと考えています。

この問題は、ネットワーク フローを使用して定式化できると思います。ノードが繰り返される場合、フローを 0 または無限大にする同じ色のノードに何らかのペナルティを課すことができます。

ありがとう！

頂点 A と B の 2 つのセットを持つ 2 部グラフがあります。エッジには重みがありません。ただし、セットの 1 つ (セット B など) の頂点には正の重みが割り当てられています (wb1、wb2...) セットから一致する頂点の重みの合計を最大化するために、この 2 部グラフで一致を見つけたいB.

大規模なオンライン検索の後、これが私が思いついたものです。頂点biにあるすべてのエッジに重みwbiを割り当て、ハンガリーのアルゴリズムを実行します。加重最大マッチングとは異なるため、この問題をより効率的に調べる方法はありますか (ここでは、頂点にはエッジではなく重みがあります)。

私の言語が明確でない場合は、自由に編集してください。ありがとうございました。

これが重複していないことを願っていますが、この問題に対する具体的な答えが見つからないようです。私はPythonにかなり慣れていないので、明らかかもしれませんが、エラーを見つけることができないようです。

問題は次のとおりです。ネットワークフローモデルを最適化するために gurobi を使用しています。しかし、2 つの変数を反復処理する必要があるため、制約の作成に問題があります (それが問題だと思います)。

最初のコードは次のとおりです。

機能していない部分は次のとおりです。

エラーは次のとおりです: 'Var' 型は反復可能ではありません。たとえば、Java では、p と i の 2 つのループで実行できました (Python で試してみましたが、うまくいきませんでした)。しかし、この問題を解決する方法がわかりません。パイソンで。

前もって感謝します

Dinic のアルゴリズムを動的ツリーに適用したい。しかし、ソースはほとんど見つかりません。特に動的ツリーについて。詳細な説明が記載された適切なソースや、動的ツリーを使用する簡単なソース コードがあれば素晴らしいと思います。

そのようなものに出くわした人はいますか？前もって感謝します

3 つのエッジがノードに入り、3 つのエッジが出てくるようなグラフがありますが、特定の入力エッジに容量がある場合にのみ、出力エッジをアクティブにする必要があります。たとえば、次の場合:

A -> N

B -> N

C -> N

N -> N'

N' -> A'

N' -> B'

N' -> C'

Aにフローがある場合はA'を通過するフローのみが必要であり、Bにフローがある場合はB'を通過するフローなどが必要です。

基本的に、エッジ A、B、C の容量リミッターであり、最初は容量を制限できませんでした。

この制約を最大フローに追加し、このシナリオが複数回発生すると仮定して、特定のグラフの最大フロー グラフの問題を解決するにはどうすればよいですか?

編集: A'、B'、および C' はグラフの後半で使用されるため、最終的にそれらの容量を制限することもできません。そのため、N と N' を最後に移動して、後で結合容量を強制的に小さくすることはできません。

エッジ加重無向グラフと 2 つのノード (ソースとシンクと呼ばれることが多い) があります。これらの 2 つのノードを 2 つの弱いコンポーネントに分離する、可能な限り最小の重みのエッジのセットを見つける必要があります。

Ford-Fulkerson の最大フロー アルゴリズムと、有向グラフの最大フローと最小カット関係に関する彼の定理については知っています。

また、Ford-Fulkerson の無向グラフの最大フロー アルゴリズムの修正についても知っています。これは、各無向エッジを 2 つの反対の有向エッジに置き換え、両方へのフローを同時に更新します。しかし、この変更により、max-flow-min-cut-theorem は有効ではなくなったように見えます。これは、次の無向グラフで最小カットが正しく決定されないためです。

max-flow-min-cut の定理によると、最小カットはそれらのエッジであり、フローはその容量に等しく、変更された Ford-Fulkerson によってそれはすべてのエッジであり、明らかに正しいカットではありません。

無向グラフでグローバル最小カットを見つけるためのStoer-Wagner アルゴリズムを見つけましたが、このアルゴリズムはソースとシンクを考慮せず、ノードを配置できるカットを見つけることができるため、これは私が望むものではありません。同じコンポーネント。

これら2つの指定されたノードを分離して、ソースとシンクを持つ無向グラフで最小カットを効率的に見つけることができるアルゴリズムはありますか? 前述のアルゴリズムを変更して、私のケースで機能するようにすることはできますか?

Edmonds-Karp アルゴリズムが経路 p に沿ってフロー f を増加させると言うとき、実際にフローを増加させるとはどういう意味ですか? パスに沿ってフローを送信することを意味しますか?