カット (グラフ理論)

最小サイズのカットのことを最小カットとよぶ。最大フロー最小カット定理は、最大フロー（流量）が始点と終点をそれぞれ含む頂点集合の二分割の間にあるカットエッジの重み付けの総和と等しいことを意味する。最小カット問題には多項式時間のアルゴリズムが存在し、フォード・ファルカーソンのアルゴリズムや、グラフの最大隣接順序を用いた永持・茨木のアルゴリズムがある。

無向グラフにおける最小カットのサイズは辺連結度とも呼ばれる。無向グラフのすべての最小カットはカクタスと呼ばれるグラフで表現でき、辺連結度に関するアルゴリズムにおけるデータ構造としての利用を含め様々な応用が存在する。

最小カット問題を線形計画問題として定式化したとき、双対問題は最大フロー問題である。最小カット問題と最大カット問題は双対ではないので注意されたい。

最大サイズのカットを最大カットとよぶ。最大カット問題はNP完全であり、この証明は、最大充足可能性問題からの変換で得られる。無向グラフの最大カット問題に対する既存の乱択アルゴリズムについて述べる^[1]。まず、基本的な解法は無向グラフのそれぞれの頂点を 1/2 の確率で選んで頂点集合を構成することで得られる。カットはこの操作で得られた頂点集合とそれ以外の頂点集合からなる 2 分割となる。また、Goemans と Williamson による0.878近似アルゴリズムが存在する。これは、グラフを超球面上への描画を考え、各辺重みと辺の両端点の距離の積の総和を最大化するような頂点配置の問題に帰着する解法であり半正定値計画問題を解くことで最大カットを算出する。unique games conjecture が真である限りにおいて、このアルゴリズムは最適な近似アルゴリズムと言える。

画像処理の手法の一つにグラフカットとよばれるものがある。この手法は画像処理の多くの問題はエネルギー最小化問題として定式化されるので、この問題を最小カット算出に帰着する。二値画像のノイズ除去、ステレオ、及びセグメンテーション等に用いられる。画像における画素とその隣接関係（縦横の 4 方向か斜めも含めた 8 方向）を、それぞれ頂点と双方向の有向辺に対応させて構成される有向グラフを考える。さらにその有向グラフにソースとシンクを付加して得られるフローネットワークにおける最小カットを算出する。応用ごとの具体的な定式化は [石川07] を参照されたい。