一种求解最小割集问题的新思路

摘要

从本质上来说,最小割集问题与最大流问题是同一个问题.由于后者的实用性更强,人们对它投入的关注与研究也更多,因而实际中是通过最大流问题来求最小割集问题.最大流-最小割集定理给出了一种用最大流算法求最小割集问题的方法,但在实际应用中,这种方法有时显得繁冗并有些迂回.文章首先介绍了最大流、最小割集的相关概念,然后从实际应用出发提出了一种用最大流求流图最小割集的新算法.随后证明了该算法的正确性,并举例说明了这种算法思想在其它方面的应用.