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

您当前的位置：

首页 >

文章列表页 >

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

更新时间：2023-11-28

- Sufficient and Necessary Condition for Split Graphs Completion in Geometric Constraint Solving
- Advanced Engineering Sciences Vol. 38, Issue 1, Pages: 103-108(2006)
- 作者机构：
- 作者简介：
- 基金信息：
- DOI：
  CLC：
- Published：2006，
扫描看全文
张新丽,朱大勇,陈帆.几何约束求解中分离图完备的充要条件[J].工程科学与技术,2006,38(1):103-108.

Sufficient and Necessary Condition for Split Graphs Completion in Geometric Constraint Solving. [J]. Advanced Engineering Sciences 38(1):103-108(2006)
张新丽,朱大勇,陈帆.几何约束求解中分离图完备的充要条件[J].工程科学与技术,2006,38(1):103-108. DOI：

Sufficient and Necessary Condition for Split Graphs Completion in Geometric Constraint Solving. [J]. Advanced Engineering Sciences 38(1):103-108(2006) DOI：

摘要

中文摘要: 在基于图论的几何约束求解方法中，通常是先将恰当几何约束图分解为两个完备的分离图，然后再进行下一步分解。而一个恰当几何约束图关于其最小切割图的两个分离图往往是不定约束的。针对以上问题，通过对最小切割图与分离图的自由度分析，得出了分离图的完备化的一个充分必要条件，并推导出2D和3D中恰当约束图的最小分割图中顶点元素个数的一个下限，这也是恰当约束图连通度的一个下限。并通过实例验证了所提出的充分必要条件的正确性。

Abstract

Abstract: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.

关键词

几何约束求解连通度切割图分离图分解

Keywords

geometric constraint solvingconnectivitycut graphsplit graphdecomposition

references

Fudos I,Hoffmann C M.A graph-constructive approach to solving systems of geometric constraints[J].ACM Trans Graph,1997,16(2):179-216.

Hoffmann C M,Vermeer P J.Geometric constraint solving in R2 and R3[C]//Du D Z,Huang F.Computing in Euclidean Geometry.Singapore:World Scientific,1995:266-298.

Joan-Arinyo R,Soto-Riera A,Vila-Marta S,et al.Revisiting decomposition analysis of geometric constraint graphs[C]//Proc ACM SM02.

Yang L.Distance coordinates used in geometric constraint solving[M]//Automated Deduction in Geometry.Springer-Verlag,LNAI 2930,2003:216-229.

Owen J.Algebraic solution for geometry from dimensional constraints[M]//ACM Symp.,Found of Solid Modeling.New York:ACM Press,1991:397-407.

Gao X S,Zhang G F.Geometric constraint solving based on connectivity of graph[C]//MM Research Prepringts.MMRC,AMSS,Academia,Sinica,Beijing,2002,(22):148-162.

Joan-Arinyo R,Soto-Riera A,Vila-Marta S.Tools to deal with under-constrained geometric constraint graphs[C].Workshop on Geometric Constraint Solving,Beijing,2003.

Hopcroft J E,Tarjan R E.Dividing a graph into triconnected components[R].Computer Science Department,Comell University,Ithaca,NY,USA,1973.

Chartrand G,Lesniak L.Graphs and digraphs[M].3rd ed.London:Chapman and Hall,1996.

更多指标>

Views

下载量

CNKI被引量

Alert me when the article has been cited

提交

Tools

Publicity Resources

No data

Related Author

No data

Related Institution

成都信息工程学院四川

电子科技大学计算机学院四川

西南交通大学计算机学院四川

⁰