graph - システムをバラバラなセットに分割する順列を見つけるためのグラフからの最小カット?

Question

無向システムを仮定すると、各セットが最小になるようにシステムをバラバラにする順列の要素を見つけたいグラフ。このグラフには 2 つの特別なノードがあります: 要素内に存在できないシンクとソースです。

あるグラフ G=(V,E) が与えられた場合、どのように最小カットを計算で見つけることができますか?

Answer 1

グラフから計算で最小カットを計算する方法を自由に選択してください。以下に、簡単な例、関連する研究、モデル、保存方法、補題、定理、およびこのスレッドが焦点を当てている視覚化とコンピューティングに関するものをリストします。簡単な例の次のステップは、グラフィカル モデルのパラメータ化と計算です。

Python とデカルト積を使用した簡単な例

3 つの並列がある 3x2x2 グラフを想定します。最初のブランチには 3 つのものがあり、2 つ目のブランチには 2 つのものがあり、最後のブランチには 2 つのものが含まれます。最小カットは{{1,4,6},{1,4,7},{1,5,6},{1,5,7},{2,4,6},{2,4, 7},{2,5,6},{2,5,7},{3,4,6},{3,4,7},{3,5,6},{3,5,7} } .

import itertools;

somelists = [
   [1, 2, 3],
   [4, 5],
   [6, 7]
]

print list(itertools.product(*somelists))

コンピューティング

• 一般的な質問疎な隣接行列を分析するにはどうすればよいですか? しかし、グラフはしばしばまばらであるため、関連性があります。

• 最小カットを見つけるのに役立つグラフ補数: 以下の Mathematica での試行ですが、少なくとも 10.1 で発見された Mathematicaのいくつかのバグが mincut および VertexConnectivity コマンドに関連していることに注意してください。

数学

• [カットの計算代数におけるグラフィカルなパラメトリゼーション問題]木のカットイデアルのベティ数などのカットイデアル

• [単純なグラフのグラフィカルなパラメトリゼーション問題] 一定数の頂点と一定数の頂点カットに対する単純なグラフの最小生成集合?

• ミンカットには交差基準、サボテンの保管方法、およびGraph Connectivity の論文 (2004)で概説されている現在の研究があります。

• 頂点セパレーター、分岐点、頂点カット、エッジ カット、グラフ境界など、最小カットに関連する多くの用語 -ここで概説されている数学用語。

シンクとソースを使用した直並列グラフの視覚化

• 直並列の多くの変数を持つ直並列グラフを描画する Tikz パッケージ

• 高品質の資料には、Lauritzen Steffen による「グラフィカル モデル」 、 「R のグラフィカル モデル」、および Sturmfels による代数幾何学資料が含まれています。