Table of Contents
Preface xiii
1 Introduction 1
1-1 What is a Graph? 1
1-2 Application of Graphs 3
1-3 Finite and Infinite Graphs 6
1-4 Incidence and Degree 7
1-5 Isolated Vertex, Pendant Vertex, and Null Graph 8
1-6 Brief History of Graph Theory 10
Summary 11
References 11
Problems 12
2 Paths and Circuits 14
2-1 Isomorphism 14
2-2 Subgraphs 16
2-3 A Puzzle With Multicolored Cubes 17
2-4 Walks, Paths, and Circuits 19
2-5 Connected Graphs, Disconnected Graphs, and Components 21
2-6 Euler Graphs 23
2-7 Operations On Graphs 26
2-8 More on Euler Graphs 28
2-9 Hamiltonian Paths and Circuits 30
2-10 The Traveling Salesman Problem 34
Summary 35
References 35
Problems 36
3 Trees and Fundamental Circuits 39
3-1 Trees 39
3-2 Some Properties of Trees 41
3-3 Pendant Vertices in a Tree 43
3-4 Distance and Centers in a Tree 45
3-5 Rooted and Binary Trees 48
3-6 On Counting Trees 52
3-7 Spanning Trees 55
3-8 Fundamental Circuits 57
3-9 Finding All Spanning Trees of a Graph 58
3-10 Spanning Trees in a Weighted Graph 61
Summary 64
References 64
Problems 65
4 Cut-Sets and Cut-Vertices 68
4-1 Cut-Sets 68
4-2 Some Properties of a Cut-Set 69
4-3 All Cut-Sets in a Graph 71
4-4 Fundamental Circuits and Cut-Sets 73
4-5 Connectivity and Separability 75
4-6 Network Flows 79
4-7 1-Isomorphism 80
4-8 2-Isomorphism 82
Summary 85
References 86
Problems 86
5 Planar and Dual Graphs 88
5-1 Combinatorial Vs. Geometric Graphs 88
5-2 Planar Graphs 90
5-3 Kuratowski's Two Graphs 90
5-4 Different Representations of a Planar Graph 93
5-5 Detection of Planarity 99
5-6 Geometric Dual 102
5-7 Combinatorial Dual 104
5-8 More on Criteria of Planarity 107
5-9 Thickness and Crossings 108
Summary 109
References 110
Problems 110
6 Vector Spaces of a Graph 112
6-1 Sets with One Operation 112
6-2 Sets with Two Operations 116
6-3 Modular Arithmetic and Galois Fields 118
6-4 Vectors and Vector Spaces 120
6-5 Vector Space Associated with a Graph 121
6-6 Basis Vectors of a Graph 123
6-7 Circuit and Cut-Set Subspaces 125
6-8 Orthogonal Vectors and Spaces 129
6-9 Intersection and Join of W and Ws 131
Summary 134
References 135
Problems 135
7 Matrix Representation of Graphs 137
7-1 Incidence Matrix 137
7-2 Submatrices of A(G) 141
7-3 Circuit Matrix 142
7-4 Fundamental Circuit Matrix and Rank of B 144
7-5 An Application to a Switching Network 146
7-6 Cut-Set Matrix 151
7-7 Relationships among Af, Bf, and Cf 153
7-8 Path Matrix 156
7-9 Adjacency Matrix 157
Summary 162
References 162
Problems 162
8 Coloring, Covering, and Partitioning 165
8-1 Chromatic Number 165
8-2 Chromatic Partitioning 169
8-3 Chromatic Polynomial 174
8-4 Matchings 177
8-5 Coverings 182
8-6 The Four Color Problem 186
Summary 190
References 190
Problems 192
9 Directed Graphs 194
9-1 What Is a Directed Graph? 194
9-2 Some Types of Digraphs 197
9-3 Digraphs and Binary Relations 198
9-4 Directed Paths and Connectedness 201
9-5 Euler Digraphs 203
9-6 Trees with Directed Edges 206
9-7 Fundamental Circuits in Digraphs 212
9-8 Matrices A, B, and C of Digraphs 213
9-9 Adjacency Matrix of a Digraph 220
9-10 Paired Comparisons and Tournaments 227
9-11 Acyclic Digraphs and Decyclization 230
Summary 233
References 234
Problems 234
10 Enumeration of Graphs 238
10-1 Types of Enumeration 238
10-2 Counting Labeled Trees 240
10-3 Counting Unlabeled Trees 241
10-4 Pólya's Counting Theorem 250
10-5 Graph Enumeration With Pólya's Theorem 260
Summary 264
References 264
Problems 265
11 Graph Theoretic Algorithms and Computer Programs 268
11-1 Algorithms 269
11-2 Input: Computer Representation of a Graph 270
11-3 The Output 273
11-4 Some Basic Algorithms 274
Algorithm 1 Connectedness and Components 274
Algorithm 2 A Spanning Tree 277
Algorithm 3 A Set of Fundamental Circuits 280
Algorithm 4 Cut-Vertices and Separability 284
Algorithm 5 Directed Circuits 287
11-5 Shortest-Path Algorithms 290
Algorithm 6 Shortest Path from a Specified Vertex to Another Specified Vertex 292
Algorithm 7 Shortest Path between All Pairs of Vertices 297
11-6 Depth-First Search on a Graph 301
Algorithm 8 Planarity Testing 304
11-7 Algorithm 9: Isomorphism 310
11-8 Other Graph-Theoretic Algorithms 312
11-9 Performance of Graph-Theoretic Algorithms 314
11-10 Graph-Theoretic Computer Languages 316
Summary 317
References 318
Problems 321
Appendix of Programs 323
12 Graphs in Switching and Coding Theory 328
12-1 Contact Networks 329
12-2 Analysis of Contact Networks 330
12-3 Synthesis of Contact Networks 334
12-4 Sequential Switching Networks 342
12-5 Unit Cube and Its Graph 348
12-6 Graphs in Coding Theory 351
Summary 354
References 354
13 Electrical Network Analysis by Graph Theory 356
13-1 What Is an Electrical Network? 357
13-2 Kirchhoff's Current and Voltage Laws 358
13-3 Loop Currents and Node Voltages 359
13-4 RLC Networks with Independent Sources: Nodal Analysis 362
13-5 RLC Networks with Independent Sources: Loop Analysis 371
13-6 General Lumped, Linear, Fixed Networks 373
Summary 379
References 381
Problems 381
14 Graph Theory in Operations Research 384
14-1 Transport Networks 384
14-2 Extensions of Max-Flow Min-Cut Theorem 390
14-3 Minimal Cost Flows 393
14-4 The Multicommodity Flow 395
14-5 Further Applications 396
14-6 More on Flow Problems 397
14-7 Activity Networks in Project Planning 400
14-8 Analysis of an Activity Network 402
14-9 Further Comments on Activity Networks 408
14-10 Graphs in Game Theory 409
Summary 414
References 414
15 Survey of Other Applications 416
15-1 Signal-Flow Graphs 416
15-2 Graphs in Markov Processes 424
15-3 Graphs in Computer Programming 439
15-4 Graphs in Chemistry 449
15-5 Miscellaneous Applications 454
Appendix A Binet-Cauchy Theorem 458
Appendix B Nullity of a Matrix and Sylvester's Law 460
Index 463