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

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

A New Method for the Minimum Cut Problem

Essentially speaking,the mi ni mum cut problem is the same problem as the maximum flow problem.People pay mo re attention to and plunge more research into the latter because of its more pra ctical use,and thus always solve the minimum cut problem by means of the maxim um flow algorithm.The max-flow-min-cut theorem gives a method for the minim um cut problem using maximum flow algorithm.But unfortunately,this method so metimes seems tedious and,to some degree,indirect.At first this paper expo unds the concept of the minimum cut problem and the maximum flow problem,then pre sents a new method to solve the minimum cut problem of flow network using maximum flow algorithm.Finally it proves the correction of this algorithm and g ives an example to explain the application of the method on some other sides.