最小カット

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

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

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

終端ノードなし

重み付き無向グラフ（非負の重みに限定）における最小カット問題は、ストアー・ワグナーアルゴリズムによって多項式時間で解くことができます。グラフが重み付けされていない特殊なケースでは、カーガーアルゴリズムがカットを見つけるための効率的なランダム化手法を提供します。この場合、最小カットはグラフの辺の連結性に等しくなります。

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

末端ノード付き

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

重み付き無向ネットワークでは、特定の頂点ペアを分離し、かつ重みが最小となるカットを計算することが可能です。この問題をあらゆる可能な頂点ペアに対して解くカット体系は、グラフのゴモリー・フー木と呼ばれる構造にまとめることができます。

端子付き最小カット問題の一般化は $k$ 端子カット、あるいは多端子カットである。平面グラフでは、この問題は多項式時間で解ける。しかし、一般にこの問題はであってもNP困難である。^[³^] $k=3$

アプリケーション

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