グラフ理論 において、グラフ G (V , E ) の頂点 V の 2 分割 (S , T ) をカット （英 : Cut ）とよぶ。このとき、ある辺 (u ,v )
∈ ∈ -->
{\displaystyle \in }
E の端点が u
∈ ∈ -->
{\displaystyle \in }
S かつ v
∈ ∈ -->
{\displaystyle \in }
T （有向グラフの場合 u
∈ ∈ -->
{\displaystyle \in }
T でかつ v
∈ ∈ -->
{\displaystyle \in }
S の場合もある）であるとき、この辺を「カットエッジ」と呼ぶ。
カットのサイズ (カットの重み) は、カットエッジの総数 (辺重みグラフの場合はカットエッジそれぞれの辺重みの総和) で表される。フローネットワーク では、カットのサイズは始点側から終点側へ向かう辺重みの総和で定義される（逆方向のエッジは加算されない）。
頂点集合のべき集合を定義域としたカットのサイズを返す集合関数は「カット関数」と呼ばれ、
劣モジュラ関数 、かつ、正モジュラ関数 である。
最小カット 最大カット 最小サイズのカットのことを最小カットとよぶ。最大フロー最小カット定理 は、最大フロー（流量）が始点と終点をそれぞれ含む頂点集合の 2 分割の間にあるカットエッジの重み付けの総和と等しいことを意味する。最小カット問題には多項式時間 のアルゴリズム が存在し、フォード・ファルカーソンのアルゴリズム や、グラフの最大隣接順序 を用いた永持・茨木のアルゴリズム がある。
無向グラフにおける最小カットのサイズは辺連結度 とも呼ばれる。 無向グラフのすべての最小カットはカクタスと呼ばれるグラフで表現でき、辺連結度に関するアルゴリズムにおけるデータ構造としての利用を含め様々な応用が存在する。
最小カット問題を線形計画問題 として定式化したとき、双対問題は最大フロー問題 である。最小カット問題と最大カット問題は双対ではないので注意されたい。
最大サイズのカットを最大カットとよぶ。最大カット問題はNP完全 であり、この証明は、最大充足可能性問題 からの変換で得られる。無向グラフの最大カット問題に対する既存の乱択アルゴリズム [ 1] 半正定値計画問題 を解くことで最大カットを算出する。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
S. Khot, G. Kindler, E. Mossel, and R. O’Donnell, Optimal inapproximability results for MAX-CUT and other two-variable CSPs?
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 H. Nagamochi, and T. Ibaraki, Algorithmic Aspects of Graph Connectivity , Cambridge University Press, Cambridge, (2008)
石川, グラフカット (チュートリアル) 情報処理学会研究報告. CVIM, 2007(31), 193-204, (2007)
^ 松井知己 (2000), “半正定値計画を用いた最大カット問題の.878近似解法”, オペレーションズ・リサーチ 45 (3): 140-145
