カット (グラフ理論)
最小サイズのカットのことを最小カットとよぶ。最大フロー最小カット定理は、最大フロー(流量)が始点と終点をそれぞれ含む頂点集合の 2 分割の間にあるカットエッジの重み付けの総和と等しいことを意味する。最小カット問題には多項式時間のアルゴリズムが存在し、フォード・ファルカーソンのアルゴリズムや、グラフの最大隣接順序を用いた永持・茨木のアルゴリズムがある。
無向グラフにおける最小カットのサイズは辺連結度とも呼ばれる。 無向グラフのすべての最小カットはカクタスと呼ばれるグラフで表現でき、辺連結度に関するアルゴリズムにおけるデータ構造としての利用を含め様々な応用が存在する。
最小カット問題を線形計画問題として定式化したとき、双対問題は最大フロー問題である。最小カット問題と最大カット問題は双対ではないので注意されたい。