カット (グラフ理論)

グラフ理論において、グラフ G(V, E) の頂点 V の 2 分割 (S, T) をカット（英: Cut）とよぶ。このとき、ある辺 (u,v) $\in$ E の端点が u $\in$ S かつ v $\in$ T（有向グラフの場合 u $\in$ T でかつ v $\in$ S の場合もある）であるとき、この辺を「カットエッジ」と呼ぶ。

カットのサイズ (カットの重み) は、カットエッジの総数 (辺重みグラフの場合はカットエッジそれぞれの辺重みの総和) で表される。フローネットワークでは、カットのサイズは始点側から終点側へ向かう辺重みの総和で定義される（逆方向のエッジは加算されない）。

頂点集合のべき集合を定義域としたカットのサイズを返す集合関数は「カット関数」と呼ばれ、 劣モジュラ関数、かつ、正モジュラ関数である。

最小カットと最大カット

最小カット

最小カット

最大カット

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

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

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

最大カット

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

応用

グラフカット

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

関連項目

カット構造

• ゴモリ・フー木
• 極点集合

その他

• 連結グラフ
• メンガーの定理
• 劣モジュラ関数

参考文献

• R. M. Karp, Reducibility among combinatorial problems, in R. E. Miller and J. W. Thacher (eds.), Complexity of Computer Computation, Plenum Press, New York, 85-103 (1972)
• M. X. Goemans, and D. P. Williamson, Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming, Journal of the ACM, 42, 6 (Nov. 1995), 1115-1145
• S. Khot, G. Kindler, E. Mossel, and R. O’Donnell, Optimal inapproximability results for MAX-CUT and other two-variable CSPs?, In Proceedings of the 45th IEEE Symposium on Foundations of Computer Science, pp. 146–154, 2004.
• Michael R. Garey and David S. Johnson (1979年). Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman. ISBN 0-7167-1045-5  A2.2: ND16, pg.210.
• H. Nagamochi, and T. Ibaraki, Algorithmic Aspects of Graph Connectivity, Cambridge University Press, Cambridge, (2008)
• 石川, グラフカット (チュートリアル) 情報処理学会研究報告. CVIM, 2007(31), 193-204, (2007)