求图的约束最小割集的一个有效算法及其应用

摘要

本文提出确定把无向连通图G（V,E）切割为两个子图G1（V1,E1）和G2（V2,E2）且满足顶点集V1和V2的顶点数|V1|和|V2|为给定值的约束最小割集的一种有效算法。该算法理论比较简单,步骤简捷有效,并能保证在多项式时间内获得最优解;此外,本文举例说明该算法具体步骤过程并介绍该算法在计算机辅助电路分析和设计中的某些实际应用。