カット (グラフ理論)
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2025/08/02 13:09 UTC 版)
グラフ理論において、グラフ G(V, E) の頂点 V の 2 分割 (S, T) をカット（英: Cut）とよぶ。このとき、ある辺 (u,v) 
最小サイズのカットのことを最小カットとよぶ。最大フロー最小カット定理は、最大フロー（流量）が始点と終点をそれぞれ含む頂点集合の二分割の間にあるカットエッジの重み付けの総和と等しいことを意味する。最小カット問題には多項式時間のアルゴリズムが存在し、フォード・ファルカーソンのアルゴリズムや、グラフの最大隣接順序を用いた永持・茨木のアルゴリズムがある。
無向グラフにおける最小カットのサイズは辺連結度とも呼ばれる。無向グラフのすべての最小カットはカクタスと呼ばれるグラフで表現でき、辺連結度に関するアルゴリズムにおけるデータ構造としての利用を含め様々な応用が存在する。
最小カット問題を線形計画問題として定式化したとき、双対問題は最大フロー問題である。最小カット問題と最大カット問題は双対ではないので注意されたい。
最大カット
最大サイズのカットを最大カットとよぶ。最大カット問題はNP完全であり、この証明は、最大充足可能性問題からの変換で得られる。無向グラフの最大カット問題に対する既存の乱択アルゴリズムについて述べる[1]。まず、基本的な解法は無向グラフのそれぞれの頂点を 1/2 の確率で選んで頂点集合を構成することで得られる。カットはこの操作で得られた頂点集合とそれ以外の頂点集合からなる 2 分割となる。また、Goemans と Williamson による0.878近似アルゴリズムが存在する。これは、グラフを超球面上への描画を考え、各辺重みと辺の両端点の距離の積の総和を最大化するような頂点配置の問題に帰着する解法であり半正定値計画問題を解くことで最大カットを算出する。unique games conjecture が真である限りにおいて、このアルゴリズムは最適な近似アルゴリズムと言える。
応用
グラフカット
画像処理の手法の一つにグラフカットとよばれるものがある。この手法は画像処理の多くの問題はエネルギー最小化問題として定式化されるので、この問題を最小カット算出に帰着する。二値画像のノイズ除去、ステレオ、及びセグメンテーション等に用いられる。画像における画素とその隣接関係（縦横の 4 方向か斜めも含めた 8 方向）を、それぞれ頂点と双方向の有向辺に対応させて構成される有向グラフを考える。さらにその有向グラフにソースとシンクを付加して得られるフローネットワークにおける最小カットを算出する。応用ごとの具体的な定式化は [石川07] を参照されたい。
脚注
- ^ 松井知己「半正定値計画を用いた最大カット問題の.878近似解法」『オペレーションズ・リサーチ』第45巻第3号、2000年、140-145頁。
参考文献
- 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)
関連項目
- カット構造
- その他
「カット (グラフ理論)」の例文・使い方・用例・文例
- 髪を短くカットしてもらった
- その映画はテレビ放送のために一部カットされた
- ダイヤモンドをさまざまな形にカットする
- 皆が笑い始めたとき監督は「カット」と大声で叫んだ
- あるカットから次のカットへ切り変わる
- あの店ではカットとシャンプーで20ドルしかかからない
- 大幅な賃金カット
- ブリリアントカット
- カットアンドペースト操作
- カットグラス
- カットされた宝石
- ノーカット完全版映画
- アンディーのパスはカットされた
- CMをカットするためにテープを早送りした
- コストカットの実現が今年の目標だ。
- 効果的なカットバック
- ダカット金貨を使う
- このDVDには映画のカットした場面やデリーテッドシーンが収録されています。
- 製鋼所工員たちは賃金カットに反対してストライキを行った。
- 木版の末章余白のカット
- カット (グラフ理論)のページへのリンク
