关键词: 图, 割集, 边收缩图, 递归收缩算法, 支点

Abstract: 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 results of theoretical analysis and experimental comparisons show that the adoption of the new disposal strategy improves the stability of the recursive contraction algorithm.

Key words: graph, cutset, edge contraction, recursive contraction algorithm, pivot vertex