Def.1

• 頂点集合 $V$ を 2 つの部分集合 $S$, $\ol{S}$ に分けたとき、 $D$ の弧のうち、 $S$ の頂点から $\ol{S}$ の頂点に至るもの全ての集合を $(S,\ol{S})$ と表す。
• 特に、$S$ が入口 $v$ を含み、$\ol{S}$ が出口 $w$ を含むとき、 この形に書ける弧の集合 $K=(S,\ol{S})$ を「( ネットワーク $N$ の ) カット」と呼ぶ。

Ex.2　次のネットワークではカットは 4 通りあります。

---

$\require{color}\textcolor{blue}{S=\{\,v\,\}}$, $\textcolor{green}{\ol{S}=\{\,x,y,w\,\}}$ のとき、 赤い辺たちがカット $\textcolor{red}{K=(S,\ol{S})}$ です。

	→
$\textcolor{red}{K=(S,\ol{S})=\{\,vx,vy\,\}}$		$D-K$

---

$\textcolor{blue}{S=\{\,v,x\,\}}$, $\textcolor{green}{\ol{S}=\{\,y,w\,\}}$ のときは

	→
$\textcolor{red}{K'=(S,\ol{S})=\{\,vy,xy,xw\,\}}$		$D-K'$

---

$\textcolor{blue}{S=\{\,v,y\,\}}$, $\textcolor{green}{\ol{S}=\{\,x,w\,\}}$ のときは $D-K''$ に弧 $xy$ が残りますが、 向きが $\ol{S}$ から $S$ へ向かっているのでやはり $v$-$w$ 道はありません。

	→
$\textcolor{red}{K''=(S,\ol{S})=\{\,vx,yw\,\}}$		$D-K''$

---

$\textcolor{blue}{S=\{\,v,x,y\,\}}$, $\textcolor{green}{\ol{S}=\{\,w\,\}}$ のとき

	→
$\textcolor{red}{K'''=(S,\ol{S})=\{\,xw,yw\,\}}$		$D-K'''$

Rem.3 　教科書 p.185 では 「 $D-K$ が $v$-$w$ 道を含まないこと」 を「カット」の定義としていますので、 「Def.1 のカット」は「教科書のカット」のうち極小なもの、 ということになります。

Def.4　

• $D$ 上の重み $f$ と、弧の部分集合 $B$ に対し、 $B$ に属する弧の重みの総和を $\dps{f(B)=\sum_{a \in B} f(a)}$ と表す。
• 特にカット $K=(S,\ol{S})$ に属する弧の容量の総和 $\Psi(K)$ を「カット $K$ の容量」と呼ぶ。
• $N$ のカットの中で容量が最小のものを「$N$ の最小カット」と呼ぶ。