Graph Theory with Applications to Engineering and Computer Science

by Narsingh Deo

Overview

This outstanding introductory treatment of graph theory and its applications has had a long life in the instruction of advanced undergraduates and graduate students in all areas that require knowledge of this subject. The first nine chapters constitute an excellent overall introduction, requiring only some knowledge of set theory and matrix algebra. Topics include paths and circuits, trees and fundamental circuits, planar and dual graphs, vector and matrix representation of graphs, and related subjects.
The remaining six chapters are more advanced, covering graph theory algorithms and computer programs, graphs in switching and coding theory, electrical network analysis by graph theory, graph theory in operations research, and more. Instructors may combine these chapters with the preceding material for courses in a variety of fields, including electrical engineering, computer science, operations research, and applied mathematics.

Product Details

ISBN-13:	9780486807935
Publisher:	Dover Publications
Publication date:	08/17/2016
Edition description:	First Edition, First
Pages:	496
Product dimensions:	6.00(w) x 8.90(h) x 0.70(d)

About the Author

Narsingh Deo holds the Charles N. Millican Eminent Scholar's Chair in Computer Science and is the Director of the Center for Parallel Computation at the University of Central Florida, Orlando. Previously he was Professor of Computer Science at Washington State University, where he also served as the Department Chair.

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 A_f, B_f, and C_f 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