这个想法归因于Greig，Porteous和Seheult。将矩阵视为具有电容能力的有向图，其顶点对应于矩阵条目，并且从每个顶点到其四个邻居的弧均具有容量
b 。引入另外两个顶点，一个源和一个汇点，以及一个容量为 a的 弧：从源到具有相应0条目的每个顶点，再从每个顶点具有相应1条目的容量 到
弧。找到最小切割；更改后值为0的条目是剪切的源侧的顶点，而更改后值为1的条目是剪切的宿侧的顶点。

削减成本正是您的目标。的能力的 一个 从源弧，那些跨越切口对应于从0变为1的能力的 一个 到水槽弧，那些跨越切口对应于从1变为0的能力的 b
弧，穿过切口的弧对应于从0到1的弧的情况。