カット (グラフ理論)のソースを表示

[[グラフ理論]]において、グラフ ''G''(''V'', ''E'') の頂点 ''V'' の 2 分割 (''S'', ''T'') を'''カット'''（{{lang-en-short|Cut}}）とよぶ。このとき、ある辺 (''u'',''v'') <math>\in</math> ''E'' の端点が ''u'' <math>\in</math> ''S'' かつ ''v'' <math>\in</math> ''T''（有向グラフの場合 ''u'' <math>\in</math> ''T'' でかつ ''v'' <math>\in</math> ''S'' の場合もある）であるとき、この辺を「カットエッジ」と呼ぶ。

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

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

== 最小カットと最大カット ==

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

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

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

=== 最大カット ===
最大サイズのカットを最大カットとよぶ。最大カット問題は[[NP完全]]であり、この証明は、[[最大充足可能性問題]]からの変換で得られる。無向グラフの最大カット問題に対する既存の[[乱択アルゴリズム]]<ref>{{Citation |author=松井知己 |date=2000 |title=半正定値計画を用いた最大カット問題の.878近似解法 |journal=オペレーションズ・リサーチ |volume=45 |issue=3 |pages=140-145 }}</ref>について述べる。
まず、基本的な解法は無向グラフのそれぞれの頂点を 1/2 の確率で選んで頂点集合を構成することで得られる。カットはこの操作で得られた頂点集合とそれ以外の頂点集合からなる 2 分割となる。また、Goemans と Williamson による0.878近似アルゴリズムが存在する。これは、グラフを超球面上への描画を考え、各辺重みと辺の両端点の距離の積の総和を最大化するような頂点配置の問題に帰着する解法であり[[半正定値計画問題]]を解くことで最大カットを算出する。[[:en:unique games conjecture|unique games conjecture]] が真である限りにおいて、このアルゴリズムは最適な[[近似アルゴリズム]]と言える。

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

== 脚注 ==
{{脚注ヘルプ}}
{{Reflist}}

== 参考文献 ==
*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, [http://portal.acm.org/citation.cfm?id=227684 ''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, [https://www.cs.cmu.edu/~odonnell/papers/maxcut.pdf ''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.
*{{cite book|author = Michael R. Garey and David S. Johnson | date = 1979年 | title = Computers and Intractability: A Guide to the Theory of NP-Completeness | publisher = W.H. Freeman | id = 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)
*[https://cir.nii.ac.jp/crid/1520290884508315008 石川, グラフカット（チュートリアル）情報処理学会研究報告. CVIM, 2007(31), 193-204, (2007)]

== 関連項目 ==
=== カット構造 ===
* [[ゴモリ・フー木]]
* [[極点集合]]
=== その他 ===
* [[連結グラフ]]
* [[メンガーの定理]]
* [[劣モジュラ関数]]

{{DEFAULTSORT:かつと}}
[[Category:グラフ理論]]
[[Category:数学に関する記事]]