Cartesian, curvilinear, and other unstructured grids are used for the numerical solution of ordinary and partial differential equations using finite difference, finite element, finite volume, and related methods. Graphs are broadly defined as finite or infinite sets of vertices connected by edges in structured or unstructured configurations. Infinite lattices and tiled surfaces are described by highly ordered graphs parametrized by an appropriate number of indices. Networks consist of nodes connected by physical or abstract links with an assigned conductance in spontaneous or engineered configurations. In physical and engineering applications, networks are venues for conducting or convecting a transported entity, such as heat, mass, or digitized information according to a prevailing transport law. The performance of networks is an important topic in the study of complex systems with applications in energy, material, and information transport.
The analysis of grids, graphs, and networks involves overlapping and complementary topics that benefit from a unified discussion. For example, finite difference and finite element grids can be regarded as networks whose link conductance is determined by the differential equation whose solution is sought as well as by the chosen finite difference or finite element approximation. Particular topics of interest include the properties of the node adjacency, Laplacian, and Kirchhoff matrices; the evaluation of percolation thresholds for infinite, periodic, and finite systems; the computation of the regular and generalized lattice Green's function describing the response to a nodal source; the pairwise resistance of any two nodes; the overall characterization of the network robustness; and the performance of damaged networks with reference to operational and percolation thresholds.
My goal in this text is to provide a concise and unified introduction to grids, graphs, and networks to a broad audience in the engineering, physical, biological, and social sciences. The approach is practical, in that only the necessary theoretical and mathematical concepts are introduced. Theory and computation are discussed alongside, and formulas amenable to computer programming are provided. The prerequisite is familiarity with college-level linear algebra, calculus, and elementary numerical methods.
One important new concept is the distinction between isolated and embedded networks. The former stand in isolation as though they were suspended in vacuum, whereas the latter are connected to exterior nodes where a nodal potential, such as temperature, pressure, or electrical voltage, is specified. Regular Green's functions describing the discrete field due to a nodal impulse are available in the case of embedded or infinite networks, whereas generalized Green's functions describing the discrete field due to a nodal impulse in the presence of distributed sinks are available in the case of isolated networks. Discrete Green's functions can be used as building blocks for computing general solutions subject to given constraints.
This book is suitable for self-study and as a text in an upper-level undergraduate or entry-level graduate course in sciences, engineering, and applied mathematics. The material serves as a reference of terms and concepts and as a resource of topics for further study.

Preface xi

1. One-Dimensional Grids 1

1.1. Poisson Equation in One Dimension 1

1.2. Dirichlet Boundary Condition at Both Ends 3

1.3. Neumann-Dirichlet Boundary Conditions 6

1.4. Dirichlet-Neumann Boundary Conditions 8

1.5. Neumann Boundary Conditions 10

1.6. Periodic Boundary Conditions 13

1.7. One-Dimensional Graphs 16

      1.7.1. Graph Laplacian 17

      1.7.2. Adjacency Matrix 18

      1.7.3. Connectivity Lists and Oriented Incidence Matrix 19

1.8. Periodic One-Dimensional Graphs 20

      1.8.1. Periodic Adjacency Matrix 21

      1.8.2. Periodic Oriented Incidence Matrix 22

      1.8.3. Fourier Expansions 22

      1.8.4. Cosine Fourier Expansion 24

      1.8.5. Sine Fourier Expansion 24

2. Graphs and Networks 26

2.1. Elements of Graph Theory 26

      2.1.1. Adjacency Matrix 26

      2.1.2. Node Degrees 28

      2.1.3. The Complete Graph 29

      2.1.4. Complement of a Graph 29

      2.1.5. Connectivity Lists and the Oriented Incidence Matrix 30

      2.1.6. Connected and Unconnected Graphs 30

      2.1.7. Pairwise Distance and Diameter 30

      2.1.8. Trees 31

      2.1.9. Random and Real-Life Networks 31

2.2. Laplacian Matrix 32

      2.2.1. Properties of the Laplacian Matrix 33

      2.2.2. Complete Graph 34

      2.2.3. Estimates of Eigenvalues 35

      2.2.4. Spanning Trees 36

      2.2.5. Spectral Expansion 36

      2.2.6. Spectral Partitioning 36

      2.2.7. Complement of a Graph 38

      2.2.8. Normalized Laplacian 38

      2.2.9. Graph Breakup 39

2.3. Cubic Network 39

2.4. Fabricated Networks 41

      2.4.1. Finite-Element Network on a Disk 42

      2.4.2. Finite-Element Network on a Square 43

      2.4.3. Delaunay Triangulation of an Arbitrary Set of Nodes 43

      2.4.4. Delaunay Triangulation of a Perturbed Cartesian Grid 43

      2.4.5. Finite Element Network Descending from an Octahedron 44

      2.4.6. Finite Element Network Descending from an Icosahedron 45

2.5. Link Removal and Addition 46

      2.5.1. Single and Multiple Link 47

      2.5.2. Link Addition 49

2.6. Infinite Lattices 50

      2.6.1. Bravais Lattices 50

      2.6.2. Archimedean Lattices 53

      2.6.3. Laves Lattices 56

      2.6.4. Other Two-Dimensional Lattices 57

      2.6.5. Cubic Lattices 58

2.7. Percolation Thresholds 59

      2.7.1. Link (Bond) Percolation Threshold 59

      2.7.2. Node Percolation Threshold 61

      2.7.3. Computation of Percolation Thresholds 62

3. Spectra of Lattices 67

3.1. Square Lattice 67

      3.1.1. Isolated Network 68

      3.1.2. Periodic Strip 69

      3.1.3. Doubly Periodic Network 73

      3.1.4. Doubly Periodic Sheared Network 77

3.2. Möbius Strips 79

      3.2.1. Horizontal Strip 80

      3.2.2. Vertical Strip 83

      3.2.3. Klein Bottle 84

3.3. Hexagonal Lattice 86

      3.3.1. Isolated Network 87

      3.3.2. Doubly Periodic Network 89

      3.3.3. Alternative Node Indexing 92

3.4. Modified Union Jack Lattice 93

      3.4.1. Isolated Network 94

      3.4.2. Doubly Periodic Network 99

3.5. Honeycomb Lattice 98

      3.5.1. Isolated Network 99

      3.5.2. Brick Representation 101

      3.5.3. Doubly Periodic Network 102

      3.5.4. Alternative Node Indexing 110

3.6. Kagomé Lattice 111

      3.6.1. Isolated Network 112

      3.6.2. Doubly Periodic Network 115

3.7. Simple Cubic Lattice 122

3.8. Body-Centered Cubic (bcc) Lattice 124

3.9. Face-Centered Cubic (fcc) Lattice 126

4. Network Transport 130

4.1. Transport Laws and Conventions 130

      4.1.1. Isolated and Embedded Networks 130

      4.1.2. Nodal Sources 131

      4.1.3. Linear Transport 132

      4.1.4. Nonlinear Transport 133

4.2. Uniform Conductances 133

      4.2.1. Isolated Networks 134

      4.2.2. Embedded Networks 134

4.3. Arbitrary Conductances 135

      4.3.1. Scaled Conductance Matrix 136

      4.3.2. Weighed Adjacency Matrix 136

      4.3.3. Weighed Node Degrees 137

      4.3.4. Kirchhoff Matrix 138

      4.3.5. Weighed Oriented Incidence Matrix 139

      4.3.6. Properties of the Kirchhoff Matrix 139

      4.3.7. Normalized Kirchhoff Matrix 140

      4.3.8. Summary of Notation 141

4.4. Nodal Balances in Arbitrary Networks 142

      4.4.1. Isolated Networks 142

      4.4.2. Embedded Networks and the Modified Kirchhoff Matrix 142

      4.4.3. Properties of the Modified Kirchhoff Matrix 143

4.5. Lattices 145

      4.5.1. Square Lattice 145

      4.5.2. Möbius Strip 149

      4.5.3. Hexagonal Lattice 150

      4.5.4. Modified Union Jack Lattice 150

      4.5.5. Simple Cubic Lattice 151

4.6. Finite Difference Grids 156

4.7. Finite Element Grids 156

      4.7.1. One-Dimensional Grid 156

      4.7.2. Two-Dimensional Grid 157

5. Green's Functions 161

5.1. Embedded Networks 164

      5.1.1. Green's Function Matrix 162

      5.1.2. Normalized Green's Function 163

5.2. Isolated Networks 164

      5.2.1. Moore-Penrose Green's Function 164

      5.2.2. Spectral Expansion 166

      5.2.3. Normalized Moore-Penrose Green's Function 167

      5.2.4. One-Dimensional Network 168

      5.2.5. Periodic One-Dimensional Network 169

      5.2.6. Free-Space Green's Function in One Dimension 171

      5.2.7. Complete Network 171

      5.2.8. Discontiguous Networks 172

5.3. Lattice Green's Functions 173

      5.3.1. Periodic Green's Functions 173

      5.3.2. Free-Space Green's Functions 175

5.4. Square Lattice 177

      5.4.1. Periodic Green's Function 177

      5.4.2. Free-Space Green's Function 179

      5.4.3. Helmholtz Equation Green's Function 190

      5.4.4. Kirchhoff Green's Function 190

5.5. Hexagonal Lattice 191

      5.5.1. Periodic Green's Function 191

      5.5.2. Free-Space Green's Function 192

5.6. Modified Union Jack Lattice 196

      5.6.1. Periodic Green's Function 197

      5.6.2. Free-Space Green's Function 198

5.7. Honeycomb Lattice 200

      5.7.1. Periodic Green's Function 201

      5.7.2. Free-Space Green's Function 203

5.8. Simple Cubic Lattice 206

      5.8.1. Periodic Green's Function 206

      5.8.2. Free-Space Green's Function 207

5.9. Body-Centered Cubic (bcc) Latice 209

5.10. Face-Centered Cubic (fcc) Lattice 211

5.11. Free-Space Lattice Green's Functions 212

      5.11.1. Probability Lattice Green's Function 213

5.12. Finite Difference Solution in Terms of Green's Functions 216

6. Network Performance 220

6.1. Pairwise Resistance 220

      6.1.1. Embedded Networks 221

      6.1.2. Isolated Networks 223

      6.1.3. One-Dimensional Network 225

      6.1.4. One-Dimensional Periodic Network 226

      6.1.5. Infinite Lattices 226

      6.1.6. Triangle Inequality 227

      6.1.7. Random Walks 227

6.2. Mean Pairwise Resistance 228

      6.2.1. Spectral Representation 228

      6.2.2. Complete Network 229

      6.2.3. One-Dimensional Isolated Network 229

      6.2.4. One-Dimensional Periodic Network 230

      6.2.5. Periodic Lattice Patches 231

6.3. Damaged Networks 234

      6.3.1. Damaged Kirchhoff Matrix 235

      6.3.2. Embedded Networks 236

      6.3.3. One Damaged Link 238

      6.3.4. Clipped Links 240

      6.3.5. Isolated Networks 240

6.4. Reinforced Networks 240

6.5. Damaged Lattices 242

      6.5.1. One Damaged Link 242

      6.5.2. Effective-Medium Theory 245

      6.5.3. Percolation Threshold 246

6.6. Damaged Square Lattice 247

6.7. Damaged Honeycomb Lattice 251

6.8. Damaged Hexagonal Lattice 255

      6.8.1. Longitudinal Transport 255

      6.8.2. Lateral Transport 257

Appendices

A. Eigenvalues of Matrices 259

A.1. Eigenvalues and Eigenvectors 259

A.2. The Characteristic Polynomial 260

      A.2.1. Eigenvalues, Trace, and the Determinant 261

      A.2.2. Powers, Inverse, and Functions of a Matrix 262

      A.2.3. Hermitian Matrices 262

      A.2.4. Diagonal Matrix of Eigenvalues 263

A.3. Eigenvectors and Principal Vectors 263

      A.3.1. Properties of Eigenvectors 264

      A.3.2. Left Eigenvectors 264

      A.3.3. Matrix of Eigenvectors 265

      A.3.4. Eigenvalues and Eigenvectors of the Adjoint 266

      A.3.5. Eigenvalues of Positive Definite Hermitian Matrices 266

A.4. Circulant Matrices 267

A.5. Block Circulant Matrices 268

B. The Sherman-Morrison and Woodbury Formulas 269

B.1. The Woodbury Formula 269

B.2. The Sherman-Morrison Formula 273

References 278

Index 281

中科院文献情报中心