CONTENTS Xi Contents Page number Editorial Foreword vii Preface ix List of Symbols xix 1. BASIC CONCEPTS AND DEFINITIONS OF GRAPH THEORY 1 1.1 Introduction 1 1.2 Basic Definitions 2 1.2.1 Definition of a Graph 2 1.2.2 Adjacency and Incidence 3 1.2.3 Isomorphic Graphs 3 1.2.4 Graph Operations 4 1.2.5 Walks, Trails and Paths 4 1.2.6 Connectedness 5 1.2.7 Cycles and Cutsets 6 1.2.8 Trees, Spanning Trees and Shortest Route Trees 6 1.3 Different Types of Graphs 8 1.4 Vector Spaces Associated with a Graph ., S, i; < 9 1.4.1 Group and Fields 9 1.4.2 Vector Spaces 10 1.4.3 Vector Space of a Graph 11 1.4.4 Cycle Subspace and Cutset Subspace of a Graph 12 1.4.5 Fundamental Cycle Bases 13 1.4.6 Fundamental Cutset Bases 14 1.4.7 Dimensions of Cycle and Cutset Subspaces 15 1.4.8 Orthogonality Property 16 1.5 Matrices Associated with a Graph 16 1.5.1 Matrix Representation of a Graph 17 1.5.2 Cycle Bases Matrices 20 1.5.3 Cutset Bases Matrices 22 1.6 Directed Graphs and Their Matrices 24 1.7 Graphs Associated with Matrices 25 1.8 Planar Graphs - Euler's Polyhedra Formula <o:*;.;o,/.-] 27 1.8.1 Planar Graphs 27 1.8.2 Theorems for Planarity 29 1.9 Maximal Matching in Bipartite Graphs 31 1.9.1 Definitions 31 1.9.2 Theorems on Matching jt 31 1.9.3 Maximum Matching;,, ..,. ' t> 32 xii CONTENTS Exercises 35 2. TOPOLOGICAL PROPERTIES OF SKELETAL STRUCTURES 39 2.1 Introduction 39 2.2Mathematical Model of a Skeletal Structure 40 2.3 Union-intersection Method 42 2.3.1 A Unifying Function 43 2.3.2 An Expansion Process 44 2.3.3 An Intersection Theorem 46 2.3.4 A Method for Determining the OKI and DSI of Structures 48 2.3.5 Modifications on a Structure 55 2.4 Identification Method 56 2.5 The DSI of Structures: Special Methods 59 2.6 Space Structures and Their Planar Drawings 64 2.6.1 Admissible Drawing of a Space Structure 64 2.6.2 The Degree of Statical Indeterminacy of Space Frames 65 2.6.3 The Degree of Statical Indeterminacy of Space Trusses 68 2.6.4 Comparison of Classical and Topological Formulae 71 2.7 Suboptimal Drawing of a Space Structure 74 2.7.1 Introduction 74 27.2 Automatic Drawing of a Space Structure 75 Exercises 83 3. RIGIDITY OF SKELETAL STRUCTURES 85 3.1 Introduction 85 3.2 Definitions 86 3.3 Complete Matching for the Recognition of Generic Independence 89 3.4 A Decomposition Approach for the Recognition of Generic Independence 92 3.5 Rigidity of Planar Trusses: Special Methods 94 3.5.1 Simple Trusses 94 3.5.2 Trusses in the Form of 2-trees 95 3.5.3 A y-tree and its Rigidity 96 3.5.4 Grid-form Trusses with Bracings 98 3.6 Henneberg Sequence for Examining the Rigidity of Trusses 100 3.7 Connectivity and Rigidity 102 Exercises 104 4. NETWORK FORMULATION OF STRUCTURAL ANALYSIS 107 4.1 Introduction 107 4.2 Theory of Networks 108 CONTENTS xiii 4.3 Basic Concepts of Network Theory 109 4.3.1 Topological Properties of Networks 110 4.3.2 Algebraic Properties of Networks 112 4.3.3 Formulation of Network Analysis > 118 4.4Formulation of Structural Analysis 119 Exercises 123 5. MATRIX DISPLACEMENT METHOD 125 5.1 Introduction 125 5.2Formulation 125 5.3 Element Stiffness Matrices 136 5.3.1 Stiffness Matrix of a General Element 136 5.3.2 Stiffness Matrix of a Bar Element 138 5.3.3 Stiffness Matrix of a Beam Element 'i142 5.4Overall Stiffness Matrix of a Structure ,'l i 145 5.5General Loading o 151 5.6Computational Aspects of the Matrix Displacement Method 153 Exercises 155 6. MATRIX FORCE METHOD' A 159 6.1 Introduction .-. 159 6.2Formulation .', 160 6.3Generalized Cycle Bases of a Graph 165 6.4Minimal and Optimal Generalized Cycle Bases 168 6.5Pattern Equivalence of Flexibility and Cycle Adjacency Matrices 169 6.6MinimalGCBofaGraph 169 6.7Selection of a Subminimal GCB: Practical Methods 170 6.7.1 Method 1.1.0! r 170 6.7.2 Method 2 ' ' 171 6.7.3 Method3 171 6.8Force Method for the Analysis of Rigid-jointed Skeletal Structures I ; 172 6.8.1 Cycle Bases Selection: Topological Methods : i v 173 6.8.2 Cycle Bases Selection: Graph-theoretical Methods 178 6.8.2.1 Suboptimal Cycle Bases; A direct Approach 186 6.8.2.2 Suboptimal Cycle Bases; An Indirect Approach 188 6.8.2.3 Examples 189 6.8.3 Formation of B0 and BI Matrices 192 6.9 Force Method for the Analysis of Pin-jointed Planar Trusses 197 6.9.1 Associate Graphs for Selection of a Suboptigial GCB 197 6.9.2 A Bipartite Graph for Selection of a Suboptimal GCB 200 6.10 Force Method of Analysis for General Structures 203 xiv CONTENTS 6.10.1 Algebraic Methods 203 6.11 Optimal Plastic Analysis an Design of Frames 211 6.1 1.1 Formulation 212 6. 1 1 .2 Optimal Safe Plastic Analysis of Frames 213 6.11.3 Optimal Safe Plastic Design 2 1 4 6.1 1.4 Formation of M0 and M| Matrices 216 6.11.5 Standard Mathematical Programming Formulation 2 1 7 6.11.6 Numerical Results 2 1 8 Exercises 2 1 9 7. ORDERING FOR BANDWIDTH, PROFILE AN FRONTWIDTH OPTIMISATION 221 7. 1 Introduction 22 1 7.2 Bandwidth Optimisation 223 7.3 Preliminaries 224 7.4 Pattern Equivalence of Stiffness and Cutset Adjacency Matrices 226 7.5 A Shortest Route Tree and its Properties 228 7.6 Nodal Ordering for Bandwidth Reduction 229 7.6.1 A Good Starting Node ,; .. 230 7.6.2 Primary Nodal Decomposition 235 7.6.3 Transversal P of an SRT 235 7.6.4 Nodal Ordering' ' ;ir ! ,- ?. 236 7.6.5 Examples 237 7.7 A Connectivity Coordinate System for Nodal Ordering 239 7.7.1 A Connectivity Coordinate System for Planar Graphs 239 7.7.2 A Connectivity Coordinate System for Space Graphs 240 7.8 Nodal Numbering for Profile Reduction 242 7.9 Graph-theoretical Interpretation of Gaussian Elimination 244 7. 1 0 Element Ordering for Bandwidth Optimisation of Flexibility Matrices 246 7. 1 0. 1 An Associate Graph 246 7. 1 0.2Distance Number of an Element 247 7. 1 OJElement Ordering Algorithms 248 7.10.4Example 249 7. 1 1 Ordering for Bandwidth Optimisation of Finite Element Meshes 250 7.12 Ordering Using Algebraic Graph Theory 251 7. 12.1 Definitions 251 7. 12. 2 Eigenvalues and Eigenvectors of Matrix A 252 7. 12.3Eigenvalues and Eigenvectors of Matrix L 252 7. 1 2.4A Hybrid Method for Ordering 253 7.12.5Numerical Results 254 7.12.6Discussion 260 7. 1 3 Bandwidth Reduction for Rectangular Matrices 260 7.13.1 Definitions 261 7. 13.2 Algorithms 262 CONTENTS xv 7.14 Substructuring for Double Borded Block Diagonal Form 265 7.14.1 Main Algorithm for Substructuring 266 7.14.2Simplified Algorithm for Substructuring , . 267 Exercises 268 CONDITIONING OF STRUCTURAL MATRICES , !gn! 271 8.1 Introduction 271 8.2Condition Numbers 272 8.2.1 The Ratio of Extreme Eigenvalues 272 8.2.2 Determinant of a Row - Normalized Matrix 275 8.2.3 The Ratio of Determinants . ., 276 8.3Weighted Graph and an Admissible Member ,-; 276 8.4Optimally Conditioned Cycle Bases ; ,-, < 277 8.4.1 Formulation of the Problem 279 8.5Suboptimally Conditioned Cycle Bases 279 8.5.1 Algorithms 280 8.5.2 Examples 284 8.6Optimally Conditioned Cutset Bases 288 8.6.1 Mathematical Formulation of the Problem 288 8.7Suboptimally Conditioned Cutset Bases 289 8.7.1 Algorithms 290 8.7.2 Numerical Results ,:)( 291 Exercises , 294 9. MATROIDS AND SKELETAL STRUCTURES 297 9.1 Introduction 297 9.2Axiom Systems for a Matroid 298 9.2.1 Definition in terms of Independence ,, 298 9.2.2 Definition in terms of Bases .', 298 9.2.3 Definition in terms of Circuits ' 299 9.2.4 Definition in terms of Rank 299 9.3Matroids Relevant to Structural Mechanics 301 9.3.1 A Basis for a Finite Vector Space 301 9.3.2 A Basis for Cycle Space of a Graph 301 ' 9.3.3 A Basis for Cutset Space of a Graph 302 9.3.4 Cycle Matroid of a Graph 303 9.3.5 Cocycle Matroid of a Graph 304 9.3.6 Rigidity Matroid of a Graph 305 9.3.7 Matroid for Null Basis of a Matrix ! 305 9.4Combinatorial Optimisation: the Greedy Algorithm 306 9.5 Application of the Greedy Algorithm: A Combinatorial Force Method ; 308 9.6 Problems with Application of the Greedy Algorithm '' xvi CONTENTS 9.6.1 Planar and Space Frames 9.6.2 Planar Trusses ''311 9.6.3 Space Trusses 311 9.7 Formation of Sparse Null Bases 312 9.7.1 Definitions 312 9.7.2 Null Bases Formation 312 Exercises 314 10 A GRAPH-THEORETICAL APPROACH FOR CONFIGURATION PROCESSING 317 10.1 Introduction 317 10.2 Algebraic Representation of a Graph 318 10.3 Representations of Operations on Graphs 321 10.3.1 Addition of Two Subgraphs 321 10.3.2Subtraction of Two Subgraphs 322 10.4 Special Graphs 324 10.5 Some Functions for Configuration Processing 325 10.5.1 Translation Functions 326 10.5.2Rotation Functions ' 329 10.5.3Reflection Functions 334 10.5.4Projection Functions 336 10.6 Geometry of Structures 339 10.7 Extension to Hypergraphs 341 Exercises 344 11. GRAPH SYMMETRY FOR EIGENSOLUTION OF DYNAMIC SYSTEMS 347 11.1 Introduction 347 11.2 Decomposition of Matrices to Special Forms 348 11.2.1 Form I 348 11.2.2FormII 349 lI.2.3FormIII 350 11.3 Laplacian Matrices for Different Forms 352 11.3.1 Symmetry and Laplacian of Graphs 353 11.3.2Factorization of Symmetric Graphs , i; 355 11.3.3Form 111 as an augmented Form II 360 11.3.4Mixed Models 364 11.4 Eigenvectors of the Form II Matrices 366 11.4.1 Eigenvectors of M and Condensed Submatrices C and D 372 11.4.2Formation of Eigenvectors 373 11.5 Eigenvectors for Matrices of Form III 375 11.6 Generalized Form III Matrices 379 11.7 Vibrating Cores for a Mass-spring Vibrating System 382 CONTENTS xvii 11.8 The Graph Model of a Mass-spring system 384 11.8.1 VibratingSystem with Form II Symmetry 385 11.8.2 Vibrating System with Form III Symmetry 388 11.8.3Generalized Form III and Vibrating System 391 11.8.4Discussions 384 Exercises 385 REFERENCES 399 INDEX 415