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

【Abstract】 An efficient algorithm for finding a constrained minimum cutset of a graph is presented. The algorithm cuts the graph G(V, E) and guarantees a given number of nodes |V1| and |V2| of the two subgraphs G1(V1,.E1) and G2(V2,E2). The development and theory involved in this algorithm is unsophisticated. However it always yields an optimal solution in polynomial time (O|V|2) and it has significant applications in CAA and CAD of networks. In addition, examples to illustrate the steps of this algorithm and its applications are given.更多还原