algorithm - 最大流与最小割强对偶的含义

Question

我的问题是关于最大流量和最小切割算法。我想知道为什么最大流量和最小切割之间有很强的对偶性？

Answer 1

正如这篇Wikipedia 文章中所解释的，Max-Flow 问题和 Min-Cut 问题可以表述为对偶线性规划。由于两个线性规划都是可行的，对偶性可以看作是线性规划对偶性的一个特例。