递归收缩算法中支点的处理策略研究

为了确保生成无向图割集的递归收缩算法的正确性和稳定性，对算法中种子顶点是支点的情形进行了分析，并采取了新的处理策略。分析了支点具有一个非可吸簇的情形，引进附加吸入的概念，修正了种子顶点的BFSO值取值规则，解决了现有算法可能遗漏割集的问题。针对支点没有非可吸簇的情形，给出了一个新的处理策略，解决了现有算法在某些特殊输入条件下效率不高的问题，在理论上分析了新处理策略的有效性，并做了相应的实验比较，理论分析和实验比较均表明：新的处理策略采用提高了递归收缩算法的稳定性。

Research on strategies for disposal of pivot vertex in recursive contraction algorithm

To ensure the correctness and stability of the recursive contraction algorithm,which for generating all cutsets of a given undirected graph,the pivot cases of seed vertices are analyzed,and new disposal strategies are adopted.Firstly this paper analyzes pivot vertices which have only one inabsorbable cluster,introduces the notion of incidental absorption,corrected the rules of the setting of Breadth First Search（BFS） ordering of seed vertex,so as to solve the problem of the omission of cutset in the existing algorithm.And then,a new disposal strategy is adopted for the pivot vertices which have no inabsorbable cluster,so as to solve the problem of the inefficiency of the existing algorithm under some special circumstances of inputs.The validity of this new disposal strategy is theoretically analyzed,and the experimental comparisons are made.The re- sults of theoretical analysis and experimental comparisons show that the adoption of the new disposal strategy improves the stability of the recursive contraction algorithm.