Directed graphs, decompositions, and spatial linkages

作者：Shai Offer; Sljoka Adnan; Whiteley Walter^*

来源：Discrete Applied Mathematics, 2013, 161(18): 3028-3047.

DOI：10.1016/j.dam.2013.06.004

• Isostatic framework
• Decomposition
• Assur graphs
• Directed graph
• Algorithms

The decomposition of a linkage into minimal components is a central tool of analysis and synthesis of linkages. In this paper we prove that every pinned d-isostatic (minimally rigid) graph (grounded linkage) has a unique decomposition into minimal strongly connected components (in the sense of directed graphs), or equivalently into minimal pinned isostatic graphs, which we call d-Assur graphs. We also study key properties of motions induced by removing an edge in a d-Assur graph defining a sharper subclass of strongly d-Assur graphs by the property that all inner vertices go into motion, for each removed edge. The strongly 3-Assur graphs are the central building blocks for kinematic linkages in 3-space and the 3-Assur graphs are components in the analysis of built linkages. The d-Assur graphs share a number of key combinatorial and geometric properties with the 2-Assur graphs, including an associated lower block-triangular decomposition of the pinned rigidity matrix which provides modular information for extending the motion induced by inserting one driver in a bottom Assur linkage to the joints of the entire linkage. We also highlight some problems in combinatorial rigidity in higher dimensions (d %26gt;= 3) which cause the distinction between d-Assur and strongly d-Assur which did not occur in the plane.

• 出版日期2013-12