最小カット

グラフ理論では、グラフの最小カットまたは最小カットとは、あるメトリックにおいて最小となるカット（グラフの頂点を 2 つの互いに素な部分集合に 分割すること）のことです。

最小カット問題のバリエーションでは、重み付きグラフ、有向グラフ、端末、および頂点を 2 つ以上のセットに分割することが考慮されます。

正と負の両方の重みを許容する重み付き最小カット問題は、すべての重みの符号を反転することで、 重み付き最大カット問題に簡単に変換できます。

非負の重みに制限された無向の重み付きグラフの最小カット問題は、 Stoer-Wagner アルゴリズムによって多項式時間で解決できます。グラフが重み付けされていない特殊なケースでは、Karger のアルゴリズムによってカットを見つけるための効率的なランダム化方法が提供されます。この場合、最小カットはグラフの エッジ接続に等しくなります。

最小カット問題を末端なしで一般化したものには最小kカットがあり、その目的はできるだけ少ない辺を削除してグラフを少なくともk 個の連結成分に分割することです。 kの値が固定されている場合、この問題は多項式時間で解くことができますが、 k が大きい場合にはこのアルゴリズムは実用的ではありません。^[2]

2 つの終端ノードが指定されている場合、それらは通常、ソースとシンクと呼ばれます。フロー ネットワークでは、最小カットによってソース頂点とシンク頂点が分離され、カットのソース側からカットのシンク側に向けられたエッジの容量の合計が最小になります。最大フロー最小カット定理に示されているように、このカットの重みは、指定されたネットワークでソースからシンクに送信できるフローの最大量に等しくなります。

重み付けされた無向ネットワークでは、特定の頂点のペアを互いに分離し、重みが最小となるカットを計算することができます。すべての可能な頂点のペアに対してこの問題を解決するカットのシステムは、グラフの Gomory-Hu ツリーと呼ばれる構造にまとめることができます。

端子付き最小カット問題の一般化はk端子カット、または多端子カットである。平面グラフでは、この問題は多項式時間で解くことができる。しかし、一般にこの問題は の場合でもNP困難である。^[3]${\displaystyle k=3}$

グラフ分割問題は、グラフを2つ以上の部分に分割し、カットの両側のサイズのバランスをとるなどの追加の制約を課す組み合わせ最適化問題の一種です。セグメンテーションベースのオブジェクト分類は、正規化された最小カットスペクトルクラスタリングを画像セグメンテーションに適用した特殊なケースと見なすことができます。また、ノードがメトリック空間から取得されたと想定されるデータサンプルであり、エッジの重みがそれらの距離である一般的なクラスタリング手法としても使用できます。ただし、の計算が複雑すぎるため、これは多くの場合非現実的です。 ${\displaystyle k>2}$

最大フロー最小カット定理により、2 つのノードの最小カット値は、それらの最大フロー値に等しくなります。この場合、最大フロー問題で使用されるいくつかのアルゴリズムを使用して、この問題を解決することもできます。

頂点を持つグラフは、最大で異なる最小カットを持つことができます。この境界は、頂点上の(単純な) サイクルが正確に最小カットを持つという意味で厳密です。 ${\displaystyle n}$${\displaystyle {\binom {n}{2}}={\frac {n(n-1)}{2}}}$${\displaystyle n}$${\displaystyle {\frac {n(n-1)}{2}}}$

• 最大カット
• 頂点セパレータ、エッジではなく頂点の最小カットに類似した概念

同じ名前に関連する記事のインデックス

このセット インデックス記事には、同じ名前 (または類似の名前) を持つ関連項目のリストが含まれています。
内部リンクによって誤ってここに誘導された場合は、リンクを変更して、目的の記事に直接アクセスしてください。