Computational Technology Resources - CCP

Keywords: rigidity, graph, truss, matching, decomposition, Henneberg sequence, generic independence.

Summary

Introduction

The first combinatorial approach to the study of rigidity is due to Laman [2] who found the necessary and sufficient conditions for a graph to be rigid, when its member and nodes correspond to rigid rods (bars) and rotatable pinned-joints of a planar truss. Two main types of methods are discussed for recognizing the generic independence of graphs, which use complete matching and decomposition approaches. The Edmonds' algorithm is studied in detail and a computer code is developed based on the modified version of the Edmonds' algorithm. A second algorithm is presented based on the Henneberg sequence.

Methods for Examining the Rigidity of Trusses

Laman proved a basic theorem on rigidity as follows: The graph is generically independent if and only if for any non-empty subset of . For any subset of , is defined as , where . is stiff there exists such that and for every non-empty subset of . is stiff and generically independent if and for every non-empty subset .

This method is developed by Sugihara [3] and it is a polynomial bounded algorithm. The method uses the following theorem for the recognition. The graph model is generically independent if for any and , has a complete matching with respect to .

Lovász and Yemini [4] proved a theorem that a graph is generically independent iff doubling any member of results in a graph, which is the union of two forests. Graph is stiff and generically independent (isostatic) if doubling any member of results in a graph that is the union of two spanning trees.

References

1
A. Kaveh, Structural Mechanics: Graph and Matrix Methods, RSP (John Wiley), UK, 1995.
2
G. Laman, On graphs and rigidity of plane skeletal structures, J. Eng. Math., 4, 331ï¿½340, 1970. doi:10.1007/BF01534980
3
K. Sugihara, On some problems in the design of plane skeletal structures, SIAM J. Alg. Disc. Meth., 4, 335ï¿½362, 1983. doi:10.1137/0604035
4
L. Lovász, and Y. Yemini, On generic rigidity in the plane, SIAM J. Alg. Disc. Meth., 3, 91-98, 1982. doi:10.1137/0603009
5
J. Edmonds, Minimum partition of a matroid into independent subsets, J. Res. Nat. Bur. Standard Sect. B, 69B, 67ï¿½72,1965.

purchase the full-text of this paper (price £20)
go to the previous paper
go to the next paper
return to the table of contents
return to the book description
purchase this book (price £122 +P&P)

	Computational & Technology Resources an online resource for computational, engineering & technology publications
	not logged in - login
Front Page Browse CCP CSETS CTR IJRT Other Authors Search Purchase Guide FAQ Contact us	Civil-Comp Proceedings ISSN 1759-3433 CCP: 73 PROCEEDINGS OF THE EIGHTH INTERNATIONAL CONFERENCE ON CIVIL AND STRUCTURAL ENGINEERING COMPUTING Edited by: B.H.V. Topping Paper 15 Efficient Graph Theoretical Methods for Examining the Rigidity of Planar Trusses A. Kaveh+ and F.N. Ehsani* +Iran University of Science and Technology, Narmak, Tehran, Iran Mazandaran University of Sciences and Technologies, Babol, Iran doi:10.4203/ccp.73.15 purchase the full-text of this paper Full Bibliographic Reference for this paper A. Kaveh, F.N. Ehsani, "Efficient Graph Theoretical Methods for Examining the Rigidity of Planar Trusses", in B.H.V. Topping, (Editor), "Proceedings of the Eighth International Conference on Civil and Structural Engineering Computing", Civil-Comp Press, Stirlingshire, UK, Paper 15, 2001. doi:10.4203/ccp.73.15 Keywords:* rigidity, graph, truss, matching, decomposition, Henneberg sequence, generic independence. Summary Introduction The first combinatorial approach to the study of rigidity is due to Laman [2] who found the necessary and sufficient conditions for a graph to be rigid, when its member and nodes correspond to rigid rods (bars) and rotatable pinned-joints of a planar truss. Two main types of methods are discussed for recognizing the generic independence of graphs, which use complete matching and decomposition approaches. The Edmonds' algorithm is studied in detail and a computer code is developed based on the modified version of the Edmonds' algorithm. A second algorithm is presented based on the Henneberg sequence. Methods for Examining the Rigidity of Trusses Laman proved a basic theorem on rigidity as follows: The graph is generically independent if and only if for any non-empty subset of . For any subset of , is defined as , where . is stiff there exists such that and for every non-empty subset of . is stiff and generically independent if and for every non-empty subset . This method is developed by Sugihara [3] and it is a polynomial bounded algorithm. The method uses the following theorem for the recognition. The graph model is generically independent if for any and , has a complete matching with respect to . Lovász and Yemini [4] proved a theorem that a graph is generically independent iff doubling any member of results in a graph, which is the union of two forests. Graph is stiff and generically independent (isostatic) if doubling any member of results in a graph that is the union of two spanning trees. References 1 A. Kaveh, Structural Mechanics: Graph and Matrix Methods, RSP (John Wiley), UK, 1995. 2 G. Laman, On graphs and rigidity of plane skeletal structures, J. Eng. Math., 4, 331ï¿½340, 1970. doi:10.1007/BF01534980 3 K. Sugihara, On some problems in the design of plane skeletal structures, SIAM J. Alg. Disc. Meth., 4, 335ï¿½362, 1983. doi:10.1137/0604035 4 L. Lovász, and Y. Yemini, On generic rigidity in the plane, SIAM J. Alg. Disc. Meth., 3, 91-98, 1982. doi:10.1137/0603009 5 J. Edmonds, Minimum partition of a matroid into independent subsets, J. Res. Nat. Bur. Standard Sect. B, 69B, 67ï¿½72,1965. purchase the full-text of this paper (price £20) go to the previous paper go to the next paper return to the table of contents return to the book description purchase this book (price £122 +P&P)
Back to top	©Civil-Comp Limited 2023 - terms & conditions