几何约束求解中分离图完备的充要条件
Sufficient and Necessary Condition for Split Graphs Completion in Geometric Constraint Solving
作者：张新丽(成都信息工程学院，四川 成都610225)；朱大勇(电子科技大学 计算机学院，四川 成都 610054)；陈帆(西南交通大学 计算机学院，四川 成都 610031)
Author：(Chengdu Univ.of Info. Tech.,Chengdu 610225,China)；(School of Computer,Univ. of Electronic Sci. and Tech. of China,Chengdu 610054,China)；(School of Computer,Southwest Jiaotong Univ.,Chengdu 610031,China)
收稿日期：2005-05-27 年卷（期）页码：2006,38(1):103-108
期刊名称：工程科学与技术
Journal Name：Advanced Engineering Sciences
关键字：几何约束求解；连通度；切割图；分离图；分解
Key words：geometric constraint solving;connectivity;cut graph;split graph;decomposition
基金项目：国家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.
【关闭】
