An introduction to grids, graphs, and networks

Preface

1. One-Dimensional Grids

1.1. Poisson Equation in One Dimension

1.2. Dirichlet Boundary Condition at Both Ends

1.3. Neumann-Dirichlet Boundary Conditions

1.4. Dirichlet-Neumann Boundary Conditions

1.5. Neumann Boundary Conditions

1.6. Periodic Boundary Conditions

1.7. One-Dimensional Graphs

1.7.1. Graph Laplacian

1.7.2. Adjacency Matrix

1.7.3. Connectivity Lists and Oriented Incidence Matrix

1.8. Periodic One-Dimensional Graphs

1.8.1. Periodic Adjacency Matrix

1.8.2. Periodic Oriented Incidence Matrix

1.8.3. Fourier Expansions

1.8.4. Cosine Fourier Expansion

1.8.5. Sine Fourier Expansion

2. Graphs and Networks

2.1. Elements of Graph Theory

2.1.1. Adjacency Matrix

2.1.2. Node Degrees

2.1.3. The Complete Graph

2.1.4. Complement of a Graph

2.1.5. Connectivity Lists and the Oriented Incidence Matrix

2.1.6. Connected and Unconnected Graphs

2.1.7. Pairwise Distance and Diameter

2.1.8. Trees

2.1.9. Random and Real-Life Networks

2.2. Laplacian Matrix

2.2.1. Properties of the Laplacian Matrix

2.2.2. Complete Graph

2.2.3. Estimates of Eigenvalues

2.2.4. Spanning Trees

2.2.5. Spectral Expansion

2.2.6. Spectral Partitioning

2.2.7. Complement of a Graph

2.2.8. Normalized Laplacian

2.2.9. Graph Breakup

2.3. Cubic Network

2.4. Fabricated Networks

2.4.1. Finite-Element Network on a Disk

2.4.2. Finite-Element Network on a Square

2.4.3. Delaunay Triangulation of an Arbitrary Set of Nodes

2.4.4. Delaunay Triangulation of a Perturbed Cartesian Grid

2.4.5. Finite Element Network Descending from an Octahedron

2.4.6. Finite Element Network Descending from an Icosahedron

2.5. Link Removal and Addition

2.5.1. Single and Multiple Link

2.5.2. Link Addition

2.6. Infinite Lattices

2.6.1. Bravais Lattices

2.6.2. Archimedean Lattices

2.6.3. Laves Lattices

2.6.4. Other Two-Dimensional Lattices

2.6.5. Cubic Lattices

2.7. Percolation Thresholds

2.7.1. Link (Bond) Percolation Threshold

2.7.2. Node Percolation Threshold

2.7.3. Computation of Percolation Thresholds

3. Spectra of Lattices

3.1. Square Lattice

3.1.1. Isolated Network

3.1.2. Periodic Strip

3.1.3. Doubly Periodic Network

3.1.4. Doubly Periodic Sheared Network

3.2. Möbius Strips

3.2.1. Horizontal Strip

3.2.2. Vertical Strip

3.2.3. Klein Bottle

3.3. Hexagonal Lattice

3.3.1. Isolated Network

3.3.2. Doubly Periodic Network

3.3.3. Alternative Node Indexing

3.4. Modified Union Jack Lattice

3.4.1. Isolated Network

3.4.2. Doubly Periodic Network

3.5. Honeycomb Lattice

3.5.1. Isolated Network

3.5.2. Brick Representation

3.5.3. Doubly Periodic Network

3.5.4. Alternative Node Indexing

3.6. Kagomé Lattice

3.6.1. Isolated Network

3.6.2. Doubly Periodic Network

3.7. Simple Cubic Lattice

3.8. Body-Centered Cubic (bcc) Lattice

3.9. Face-Centered Cubic (fee) Lattice

4. Network Transport

4.1. Transport Laws and Conventions

4.1.1. Isolated and Embedded Networks

4.1.2. Nodal Sources

4.1.3. Linear Transport

4.1.4. Nonlinear Transport

4.2. Uniform Conductances

4.2.1. Isolated Networks

4.2.2. Embedded Networks

4.3. Arbitrary Conductances

4.3.1. Scaled Conductance Matrix

4.3.2. Weighed Adjacency Matrix

4.3.3. Weighed Node Degrees

4.3.4. Kirchhoff Matrix

4.3.5. Weighed Oriented Incidence Matrix

4.3.6. Properties of the Kirchhoff Matrix

4.3.7. Normalized Kirchhoff Matrix

4.3.8. Summary of Notation

4.4. Nodal Balances in Arbitrary Networks

4.4.1. Isolated Networks

4.4.2. Embedded Networks and the Modified Kirchhoff Matrix

4.4.3. Properties of the Modified Kirchhoff Matrix

4.5. Lattices

4.5.1. Square Lattice

4.5.2. Mobius Strip

4.5.3. Hexagonal Lattice

4.5.4. Modified Union Jack Lattice

4.5.5. Simple Cubic Lattice

4.6. Finite Difference Grids

4.7. Finite Element Grids

4.7.1. One-Dimensional Grid

4.7.2. Two-Dimensional Grid

5. Green's Functions

5.1. Embedded Networks

5.1.1. Green's Function Matrix

5.1.2. Normalized Green's Function

5.2. Isolated Networks

5.2.1. Moore-Penrose Green's Function

5.2.2. Spectral Expansion

5.2.3. Normalized Moore-Penrose Green's Function

5.2.4. One-Dimensional Network

5.2.5. Periodic One-Dimensional Network

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

5.2.7. Complete Network

5.2.8. Discontiguous Networks

5.3. Lattice Green's Functions

5.3.1. Periodic Green's Functions

5.3.2. Free-Space Green's Functions

5.4. Square Lattice

5.4.1. Periodic Green's Function

5.4.2. Free-Space Green's Function

5.4.3. Helmholtz Equation Green's Function

5.4.4. Kirchhoff Green's Function

5.5. Hexagonal Lattice

5.5.1. Periodic Green's Function

5.5.2. Free-Space Green's Function

5.6. Modified Union Jack Lattice

5.6.1. Periodic Green's Function

5.6.2. Free-Space Green's Function

5.7. Honeycomb Lattice

5.7.1. Periodic Green's Function

5.7.2. Free-Space Green's Function

5.8. Simple Cubic Lattice

5.8.1. Periodic Green's Function

5.8.2. Free-Space Green's Function

5.9. Body-Centered Cubic (bcc) Lattice

5.10. Face-Centered Cubic (fee) Lattice

5.11. Free-Space Lattice Green's Functions

5.11.1. Probability Lattice Green's Function

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

6. Network Performance

6.1. Pairwise Resistance

6.1.1. Embedded Networks

6.1.2. Isolated Networks

6.1.3. One-Dimensional Network

6.1.4. One-Dimensional Periodic Network

6.1.5. Infinite Lattices

6.1.6. Triangle Inequality

6.1.7. Random Walks

6.2. Mean Pairwise Resistance

6.2.1. Spectral Representation

6.2.2. Complete Network

6.2.3. One-Dimensional Isolated Network

6.2.4. One-Dimensional Periodic Network

6.2.5. Periodic Lattice Patches

6.3. Damaged Networks

6.3.1. Damaged Kirchhoff Matrix

6.3.2. Embedded Networks

6.3.3. One Damaged Link

6.3.4. Clipped Links

6.3.5. Isolated Networks

6.4. Reinforced Networks

6.5. Damaged Lattices

6.5.1. One Damaged Link

6.5.2. Effective-Medium Theory

6.5.3. Percolation Threshold

6.6. Damaged Square Lattice

6.7. Damaged Honeycomb Lattice

6.8. Damaged Hexagonal Lattice

6.8.1. Longitudinal Transport

6.8.2. Lateral Transport

Appendices

A. Eigenvalues of Matrices

A.1. Eigenvalues and Eigenvectors

A.2. The Characteristic Polynomial

A.2.1. Eigenvalues, Trace, and the Determinant

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

A.2.3. Hermitian Matrices

A.2.4. Diagonal Matrix of Eigenvalues

A.3. Eigenvectors and Principal Vectors

A.3.1. Properties of Eigenvectors

A.3.2. Left Eigenvectors

A.3.3. Matrix of Eigenvectors

A.3.4. Eigenvalues and Eigenvectors of the Adjoint

A.3.5. Eigenvalues of Positive Definite Hermitian Matrices

A.4. Circulant Matrices

A.5. Block Circulant Matrices

B. The Sherman-Morrison and Woodbury Formulas

B.1. The Woodbury Formula

B.2. The Sherman-Morrison Formula

References

Index