最小割

最小割，圖中所有的割中，邊權值和最小的割為最小割。

割

割：設Ci為網路N中一些弧的集合，若從N中刪去Ci中的所有弧能使得從源點Vs到匯點Vt的路集為空集時，稱Ci為Vs和Vt間的一個割。通俗理解，一個圖或網路的割，表示一個切面或切線，將圖或網路分為分別包含源點和漏點的兩個子集，該切線或切面與網路相交的楞或邊的集合，稱為圖像的割。

介紹

最小割：圖中所有的割中，邊權值和最小的割為最小割。

實例

實例：如右圖所示的最小割集為 --表示無序對，->表示有序對

C1：{①->③，①->⑤}

C2：{④->②， ⑤->②}

C3：{③--④，③-- ⑤，①-> ⑤}

C4：{③--④，④-- ⑤， ⑤->②}

C5：{①-> ⑤，③-- ⑤，④-- ⑤，④->②}

C6：{①->③，③- - ⑤，④-- ⑤， ⑤->②}