問題タブ [network-flow]

最大フロー問題については、いくつかの非常に洗練されたアルゴリズムがあるようで、少なくとも 1 つが昨年開発されました。Orlin の最大フローは O(mn) 時間またはそれ以上で、O(VE) で実行されるアルゴリズムを提供します。

一方、私が最も一般的に実装しているアルゴリズムは次のとおりです (徹底的な検索を行ったとは言いません。これは、何気なく観察しただけです)。

• エドモンズ・カープ、O(VE^2)
• FIFO 頂点選択を使用したプッシュ リラベル、O(V^2 E)、または O(V^3)
• Dinic のアルゴリズム、O(V^2 E)

より良い漸近実行時間を持つアルゴリズムは、現実世界の問題サイズに対して実用的ではないのでしょうか? また、「動的ツリー」がかなりの数のアルゴリズムに関与していることがわかります。これらは実際に使用されていますか？

双向グラフで中国の郵便配達回路を見つけるアルゴリズムを探しています。ここでの双向グラフは対称有向グラフではなく、1970年にEdmonds＆Johnsonによって導入されたグラフです。

ハロルド・N・ガボウがi983で発表した論文に基づいて、同様の問題を解決した論文はほとんど見つかりませんでしたが、正式なアルゴリズムはありませんでした。彼らは、問題を減らすことができる/完全なbマッチング、双方向ネットワークフローなどに関連する可能性があると述べましたが、これまでは理解できませんでした。

そのための概念とアルゴリズムを知っている人がいたら、アドバイスをください。

G = (V, E) を s と t をソースとシンクとするネットワークとします。f を G の最大フローとします。G に一意の最小カットが存在するかどうかを判断するアルゴリズムを見つけます。

このサイトで同様の質問を見つけることができました：

最小カットの一意性の決定

そこに与えられた答えの要約：

残差グラフで s から到達可能なすべての頂点を見つけると、G の最小カット (S,T) が見つかりました。

t から始まる同じ残差グラフを見てください。矢印の逆方向に t から到達可能な頂点のグループ (つまり、t に到達できるすべての頂点) を見てください。

このグループもミニカットです。

そのカットが元のカットと同一である場合は、1 つしかありません。それ以外の場合は、2 つのカットが見つかっただけなので、元のカットが一意である可能性はありません。

カットが元のカットと同一である場合、そのカットがユニークである理由がわかりません。他に最小カットがないことを誰が約束できますか?

前もって感謝します

次のようなフロー ネットワークを描画する必要があります。

誰かがそれを行うことができるプログラムを知っていますか?

グラフでは、2 点間の最短経路を見つけ、途中で 1 つのチェックポイントを訪れる必要があります。また、各頂点にアクセスできるのは 1 回だけです。ネットワークフローと関係があると思いますが、それを実装する方法がわかりません。

誰かがこの問題で私を助けてくれますか? ソリューションは明らかにネットワーク フローを使用していますが、私はネットワーク フローにあまり詳しくありません。ネットワークフローはこれをどのように解決するのに役立ちますか?

カニは 2 種類の頂点を持つ無向グラフです: 1 つの頭と K 個の足、および頭を各脚に接続する厳密に K 個の辺 (1 <= K <= T、ここで T は与えられます)。

無向グラフが与えられた場合、それぞれがクラブであるいくつかの頂点が素なサブグラフを見つける必要があります。目標は、カニがカバーする頂点の総数が最大になるような方法でカニを選択することです。

注: 2 つのグラフは、共通の頂点を持たない場合、頂点分離です。

元 。入力

私は最大の流れを独学していますが、この問題がありました：

元の問題は

• ジョブのリストがあるとします

  {J1, J1,..., Jm}

• そして、それらに応募した人々のリスト

  {P1, P2, P3,...,Pn}

• 一人一人が異なる興味を持ち、中には複数の仕事に応募した人もいます（一人一人ができる仕事のリストを持っています）

• 誰も3つ以上の仕事をすることは許されていません。

したがって、この問題は、下のグラフで最大フローを見つけることで解決できます。

この解決策は理解できましたが、

問題の難しいバージョン

これらの条件を追加するとどうなりますか？

• 簡単なバージョンの最初の 3 つの条件 (仕事と人のリスト、および各人が興味または能力のリストを持っている) は同じです。

• その会社は、Ji の仕事に Vi 人だけを雇用している

• その会社はできるだけ多くの人を雇いたい

• 人が行うことができる仕事の数に制限はありません。

私のソリューションがそれらの条件も満たすことができるようにするには、グラフにどのような違いを加える必要がありますか?または、別のアプローチが必要な場合は教えてください。

誰かが何かを言う前に、これは宿題ではありません。あくまで独学ですが、マキシマムフローを勉強していて、問題はそこにあったので、解決策はマキシマムフローを使うべきです。

Ford-Fulkerson と Edmonds-Karp など。アル。ゼロフローから始めて、それ以上増やせなくなるまで増やします。正の容量の場合。ただし、最初のゼロ フローは、正当なフローであり、容量の制約を満たすフローであることが保証されています。

負の容量では、すべてゼロのフロー割り当ては容量の制約を満たさないため、最大フローに拡張できません。

インターネット上で、負の容量を持つ最大フローは 2 つの最大フローの問題として解決できると示唆しているのを読んだことがありますが、その方法を理解することはできませんでした...

http://www.spoj.com/problems/FASTFLOW/でこの問題を解決しようとしています

この問題には dinic のアルゴリズムが適していると思います。しかし、最悪の場合、この問題には遅すぎる O(EV^2) 時間で実行されます。別のアルゴリズムまたはこのアルゴリズムの実行時間を改善するための提案はありますか?

編集: dinic のアルゴリズムの実装を含めています。どうやら、間違いが含まれているようです...誰かがテストケースを提供したり、プログラムのロジックをデバッグするのを手伝ってくれませんか.