問題タブ [minimum-cut]

私は初心者で、Java でクルスカルのアルゴリズムを使用してグラフの最小カットを見つけようとしています。

入力を読み取って、エッジのランダムな重みで vertexCount^2 個の MST を作成できる場所に到達しました。あとは、MST から、S と VS を分離するのに必要なカット数を計算するだけです。これにより、vertexCount^2 個の選択肢から最小のものを選択できます。

S と VS を取得するには、MST の最後のエッジを無視する必要があることを正しく理解していると思います。しかし、S と VS を接続しているエッジの数を把握する方法がわかりません。

したがって、私の質問は次のとおりです。2) S と VS を接続しているエッジの数を確認するにはどうすればよいですか?

PS。これは私のコードのスニペットです：

PSS。これが関連する場合、コードを書くときにhttp://algs4.cs.princeton.edu/43mst/のコードを見ました。

これは、グラフのエッジ接続とその最小カットの間の接続を尋ねる質問です。

ご存知のように、無向グラフのエッジ接続性は、kグラフを切断するために削除する必要があるエッジの最小数です。たとえば、ツリーのエッジ接続性は 1 で、サイクルのエッジ接続性は 2 です。

私の考えでは、最小限のカットの容量はエッジの接続性と等しくなければなりません。カットとは、グラフを 2 つの切断部分に分離することだからです。エッジの接続性がわかっている場合、グラフを 2 つの切断部分にするには、k少なくともエッジを削除または切断する必要があることを意味します。kしたがって、最小カットの容量は になりますk。

この質問についての結論や証拠が見つからなかったので、ここで質問します。私の考えが正しいかどうかを確認したり、他のアイデアを教えてもらえますか?

私は、有向で強く接続されたグラフであるグラフ G を持っています。グラフ内の S と T のすべてのペアを意味する、頂点のすべてのペアの最小カットを見つけるように求められます。これは、O(m ² × n ² ) 時間で実行する必要があります。

私が思いついた最善の方法は、すべての頂点を S と見なし、各 S について他のすべての頂点を T と見なし、それらのそれぞれについてフォード-フルカーソン アルゴリズムを実行し、最小カットを見つけることでした。しかし、私が間違っていなければ、このアルゴリズムは O(m ² × n ² × C) の複雑さを持ちます。

^{このタスクを O(m 2} × n ² ) 時間で行うにはどうすればよいでしょうか? それは可能ですか？

無向加重グラフがあり、頂点の 2 つのセットを分離する最小カットを見つける必要があります。2 つの頂点を分離する最小カットを見つける問題を軽減するために、セットアップを変更できます。重みが正の分数であることを付け加えておきます。

Stoer-Wagner アルゴリズムは、指定されたノードをカットの異なる側に保持すること以外はすべて行います。それを行うために SW を変更する方法があるかどうか、私は興味がありました。

ありがとうございました。

したがって、最大フローが 10 であることがわかりました。つまり、最小カットも 10 であることを意味しますが、この画像に最小カット 10 を描画するにはどうすればよいですか?

グラフ ノードを次の条件を満たす 2 つ以上のばらばらなセットに分割するアルゴリズムまたはコードはありますか。まず、エッジのみを削除できます。次に、エッジに重みが付けられ、削除されるエッジには最小の重みが必要です (最小カット アルゴリズム)。第三に、望ましいばらばらのセットは、可能な限り同じサイズを持ちます。

グラフ構造をセグメント化するためのマルチカットアルゴリズムに関するいくつかの論文を読んでいます。マルチカット問題の拡張を解決するアルゴリズムを提案するこの作品に特に興味があります。

https://www.cv-foundation.org/openaccess/content_iccv_2015/papers/Keuper_Efficient_Decomposition_of_ICCV_2015_paper.pdf

エッジコストに関しては、次のように述べています。

...ノードの任意のペアについて、これらのノードが個別のコンポーネントにあるすべての分解に対する実数値のコスト (報酬)

けっこうだ。さらに、マルチカット問題の解は、グラフ内のエッジの数に等しい長さの単純なバイナリ ベクトルであり、「1」は、対応するエッジが異なるグラフ コンポーネントに属する 2 つの頂点を分離していることを示します。

すべてのエッジ vw ∈ E ∪ F に対して、v と w が G の異なるコンポーネントにある場合に限り、y(v,w) = 1 になります。

しかし、最適化問題は次のように記述されます。

これは意味がないようです。エッジの重みが異なるコンポーネントのノードを接続するエッジの報酬を表す場合、これは最大化の問題ではないでしょうか? どちらの場合も、すべてのエッジの重みが正の場合、yベクトルがすべてゼロの自明な解が得られるのではないでしょうか? 上記の式の後にはいくつかの制約が続きますが、それらのいずれかがこの結果をどのように妨げているのかわかりませんでした。

さらに、後で貪欲な加法エッジ収縮を使用して初期ソリューションを生成しようとすると、次のように表示されます。

アルゴリズム 1は、単一ノードへの分解から始まります。繰り返しごとに、隣接するコンポーネントのペアが結合され、結合によって目的値が最大に減少します。目的の値を厳密に減少させる結合がない場合、アルゴリズムは終了します。

繰り返しますが、エッジの重みがノードを分離しておくための報酬である場合、任意の 2 つのノードを結合すると報酬が減るのではないでしょうか? そして、エッジの重みがノードを分離しておくためのペナルティであると一瞬仮定したとしても、この方法はすべてのノードを 1 つのコンポーネントにまとめるだけではないでしょうか?

これが機能する唯一の方法は、エッジの重みが正と負の値のバランスの取れた組み合わせである場合ですが、この制約は文献のどこにも言及されていないため、何かが欠けていると確信しています.