Computational & Technology Resources
an online resource for computational,
engineering & technology publications 

Computational Science, Engineering & Technology Series
ISSN 17593158 CSETS: 11
PROGRESS IN COMPUTATIONAL STRUCTURES TECHNOLOGY Edited by: B.H.V. Topping, C.A. Mota Soares
Chapter 4
The Role of Algebraic Graph Theory in Structural Mechanics A. Kaveh
Department of Civil Engineering, Iran University of Science and Technology, Tehran, Iran A. Kaveh, "The Role of Algebraic Graph Theory in Structural Mechanics", in B.H.V. Topping, C.A. Mota Soares, (Editors), "Progress in Computational Structures Technology", SaxeCoburg Publications, Stirlingshire, UK, Chapter 4, pp 77110, 2004. doi:10.4203/csets.11.4
Keywords: algebraic graph theory, Laplacian, adjacency, symmetry, eigenvalue, Fiedler vector, factors, graph product, ordering, bisection.
Summary
The representation of a finite graph by a matrix, provides
an immediate link between linear algebra and graph theory. In fact the
algebraic graph theory, in a way, can be considered as an attempt to utilize
linear algebra including the welldeveloped theory of matrices for the
purpose of graph theory and its applications. Algebraic graph theory offers
the pleasure of seeing many unexpected and useful connections between two
beautiful parts of mathematics, namely algebra and graph theory.
Algebraic graph theory can also be considered as a branch of graph theory, where eigenvalues and eigenvectors of certain matrices are employed to deduce the principal properties of a graph. In fact, eigenvalues are closely related to most of the invariants of a graph, linking one extremal property to another. These eigenvalues play a central role in fundamental understanding of graphs. The adjacency and Laplacian matrices of graphs and their eigenvalues and eigenvectors play the most important role in algebraic graph theory. These two matrices will collectively be called graph matrices. In the other hand the pattern equivalence of the graph matrices and structural matrices provide immediate connection between algebraic graph theory and structural mechanics [1,2]. One of the major contributions in algebraic graph theory is due to Fiedler [3], who introduced the properties of the second eigenvalue and eigenvector of the Laplacian of a graph. This paper consists of seven sections. After an introductory section, basic concepts and definitions are presented from algebraic graph theory in Section 2. Subsequent sections contain various applications of this theory in structural mechanics. Nodal ordering for bandwidth, profile and wavefront optimisation is discussed in Section 3. Spectral bisection is presented in Section 4 using second eigenvalue of the Laplacian matrices of graph models. Graph factorisation based on matrix algebra for different symmetric forms is discussed in Section 5, Refs [4,5]. Such factorisations have applications in studying the dynamic behaviour of massspring systems, free vibration and stability analysis of frame structures. Section 6 contains extremely fast analytical methods for evaluating eigenvalues and eigenvetors of regular structures and finite element meshes, Ref. [6]. This is based on concepts from graph products, extensively studied in the last decade. A brief discussion is provided at the end of each section, and concluding remarks form the final section of this paper. Algebra combined with the theory of graphs results in a powerful means for the solution of many problems in structural mechanics. The eigenvalues and eigenvectors of graph matrices provide a wealth of information about the topological properties of structures and finite element models. Factorisation of graph models of structures results in a considerable simplification in studying the largescale problems. The basic components of models, when identified, lead to extremely powerful tools for exploring the properties of the constituting model. References
purchase the fulltext of this chapter (price £20)
go to the previous chapter 
