几何约束求解中分离图完备的充要条件  

Sufficient and Necessary Condition for Split Graphs Completion in Geometric Constraint Solving

作　　者：张新丽[1] 朱大勇[2] 陈帆[3] 刘忠[4] 

机构地区：[1]成都信息工程学院,四川成都610225 [2]电子科技大学计算机学院,四川成都610054 [3]西南交通大学计算机学院,四川成都610031 [4]中科院成都计算所,四川成都610041

出　　处：《四川大学学报（工程科学版）》2006年第1期103-108,共6页Journal of Sichuan University (Engineering Science Edition)

基　　金：国家973计划资助项目(2004CB318003)

摘　　要：在基于图论的几何约束求解方法中,通常是先将恰当几何约束图分解为两个完备的分离图,然后再进行下一步分解。而一个恰当几何约束图关于其最小切割图的两个分离图往往是不定约束的。针对以上问题,通过对最小切割图与分离图的自由度分析,得出了分离图的完备化的一个充分必要条件,并推导出2D和3D中恰当约束图的最小分割图中顶点元素个数的一个下限,这也是恰当约束图连通度的一个下限。并通过实例验证了所提出的充分必要条件的正确性。By analyzing the degree of freedom for the cut： graphs and the split graphs, a sufficient and necessary condition for split graphs completion was presented. A lower limit of the number of elements in the set of primitives for minimal cut graphs in 2D and 3D was proposed, which is a lower limit of connectivity of structurally well-constraint graphs.

关 键 词：几何约束求解 连通度 切割图 分离图 分解 

分 类 号：TP181[自动化与计算机技术—控制理论与控制工程]