問題タブ [network-flow]

二部グラフの問題で最大マッチングに行き詰まっています。問題は次のようになります。

m 個の円形の穴があるボードと n 個の円形ディスクのセットが与えられます。穴には h ₁、...、h _m、ディスクには d ₁、...、d _nの番号が付けられます。

m 行 n 列の行列 A があります。A[i][j] = 1 は、h _{iが d j}に適合する場合(つまり、h _iの直径 ≥ d _jの直径)、それ以外の場合は 0 です。

任意の穴に最大 1 つのディスクを含めることができるという条件を考えると、穴ディスクのフィッティングが最大になる構成を見つける必要があります。

この問題はネットワーク フローの問題にモデル化できると読みましたが、その方法を正確に追うことができませんでした。誰かがこれを行う方法を説明できますか? また、私が見ることができるかもしれないこれのためのCコードはありますか?

方向付けされた重み付けされていないグラフで、個別のstカットの数を見つけようとしています。記事の中でグラフの列挙p。45これらのカットを列挙する良い方法を見つけました（セクション7.3）。そのようなカットの数だけに関心があり、実際にそれを列挙する必要がない場合に使用できる、より高速またはより単純なアルゴリズムはありますか？

私が使用しているstカットの定義は次のとおりです。2つの頂点にSとTのラベルが付いた有向グラフがあります。カットはグラフのエッジの最小セットであり、これらのエッジを削除することにより、頂点Sから頂点Tへのパスが存在しなくなります。

コストマトリックスCに割り当ての問題があります。例：

21 30 26 16 20
27 29 28 20 38
39 25 21 19 23
28 24 30 29 16
30 33 32 17 31

ここで、C [i] [j]は、ワーカーiがジョブjを実行するためのコストを意味します。

ネットワークフローアルゴリズムでこれを解決するにはどうすればよいですか？ヒントを歓迎します。

すべてのパスが同じ長さである場合、 Edmonds-Karpアルゴリズムの開始パスを選択するにはどうすればよいですか？この場合、最大フローはパスシーケンスの決定に従って変化します。

CLRS から次の補題を理解するのが困難です。

G をフロー ネットワーク、s と t をソース ノードとシンク ノード、f を s から t へのプリフロー、h を G の高さ関数とします。この場合、残差グラフ G _fには s から t への拡張パスはありません。 .

どうしてこれなの？

について話すときcomputing network flows、アルゴリズム設計マニュアルは次のように述べています。

従来のネットワークフローアルゴリズムは、パスを拡張し、sからtまでの正の容量のパスを繰り返し見つけて、それをフローに追加するという考え方に基づいています。ネットワークを通るフローは、拡張パスが含まれていない場合にのみ最適であることを示すことができます。

何なのかわかりませんaugmenting paths。私はグーグルで検索しました：

• Wolframの拡張パス

• Wikiのフローネットワーク

しかし、それらはすべて上記の引用を参照しています。

誰かが本当に明確に何であるかを説明できますaugmenting pathか？

フォードフルカーソンアルゴリズムを使用して最大フローを計算しましたが、最大を計算する必要があるプロジェクト選択問題を実装したいと考えています。番号。実行可能なプロジェクトの.i を含む min.cut を見つける必要があります。最大の利益をもたらす実行可能なプロジェクトの。分を見つけるためのアルゴリズムはどうあるべきですか。カット *グラフでmax.flowを知った後。*最大フローを使用して、ie noを含むカットを決定するにはどうすればよいですか 最大フローに貢献するノードの数。収益が最大化されるように、最適なノードのセットを選択する必要があります。私のアプリケーションでは、各ノードは収益に関連付けられており、正にも負にもなり得ます。また、優先順位の制約もあります。たとえば、a が選択されている場合は b&c も選択する必要があります。これを実装する方法を誰か教えてもらえますか?

次のように最大フロー グラフに変換しました: if Revenue(node)>0 source->node からエッジを追加します。それ以外の場合は node->sink からエッジを追加し、優先順位の制約のために無限容量のエッジを作成しました

有向グラフでソース(S)からシンク(S)へのすべての可能なパスを見つける方法は?

無向グラフG=（V、E）が与えられると、各ノードiは「Ci」個のオブジェクトに関連付けられます。各ステップで、すべてのノードiについて、Ciオブジェクトはiの隣接ノード間で均等に分割されます。Kステップ後、オブジェクトが最も多い上位5ノードのオブジェクト数を出力します。

1つのステップで行われることの1つの例を次に示します
。AのオブジェクトはBとCによって均等に分割されます。B
のオブジェクトはAとCによって均等に分割されます。C
のオブジェクトはAとBによって均等に分割されます。

いくつかの制約：| V | <10 ^ 5、| E | <2 * 10 ^ 5、K <10 ^ 7、Ci <1000

私の現在の考えは、各ステップの変換を行列で表すことです。この問題は、行列のべき乗の計算に変換されます。しかし、| V |を考慮すると、このソリューションは遅すぎます。10^5にすることができます。

それを行うためのより速い方法はありますか？

有向加重グラフが与えられた場合、頂点のすべてのペア間の最大フロー(または最小エッジ カット) を見つける方法。
単純なアプローチは、ペアごとにの複雑さを持つ Dinic のようなMax Flowアルゴリズムを呼び出すだけです。 したがって、すべてのペアで です。O((V^2)*E)
O((V^4)*E)

O((V^3)*E)いくつかO(V^3)の最適化によって複雑さを軽減することは可能ですか?