Graph Theory with Applications to Engineering & Computer Science

Graph Theory

with Applications to Engineering &

Computer Science

NARSINGH DEO

Millican Chair Professor, Dept. of Computer Science

Director, Center for Parallel Computation,

University of Central Florida

DOVER PUBLICATIONS, INC.

Mineola, New York

Copyright

Copyright © 1974 by Narsingh Deo

All rights reserved.

Bibliographical Note

This Dover edition, first published in 2016, is an unabridged republication of the work originally

published in 1974 by Prentice-Hall, Inc., Englewood Cliffs, New Jersey.

Library of Congress Cataloging-in-Publication Data Names: Deo, Narsingh 1936– Title: Graph theory with

applications to engineering and computer science / Narsingh Deo.

Description: Dover edition. | Mineola, New York: Dover Publications, 2016. Originally published:

Englewood Cliffs, New Jersey: Prentice-Hall, Inc., 1974. | Includes bibliographical references and index.

Identifiers: LCCN 2016008025 | ISBN 9780486807935 | ISBN 0486807932

Subjects: LCSH: Graphy theory. | Engineering mathematics.

Classification: LCC TA338.G7 D46 2016 | DDC 511/.5—dc23 LC record available at

http://lccn.loc.gov/2016008025

Manufactured in the United States by RR Donnelley

80793201 2016

www.doverpublications.com

To the memory of my father,

who did not live to realize his greatest ambition—

that of witnessing his eldest son matriculate.

CONTENTS

PREFACE

1 INTRODUCTION

1-1 What is a Graph?

1-2 Application of Graphs

1-3 Finite and Infinite Graphs

1-4 Incidence and Degree

1-5 Isolated Vertex, Pendant Vertex, and Null Graph

1-6 Brief History of Graph Theory

Summary

References

Problems

2 PATHS AND CIRCUITS

2-1 Isomorphism

2-2 Subgraphs

2-3 A Puzzle With Multicolored Cubes

2-4 Walks, Paths, and Circuits

2-5 Connected Graphs, Disconnected Graphs, and Components

2-6 Euler Graphs

2-7 Operations On Graphs

2-8 More on Euler Graphs

2-9 Hamiltonian Paths and Circuits

2-10 The Traveling Salesman Problem

Summary

References

Problems

3 TREES AND FUNDAMENTAL CIRCUITS

3-1 Trees

3-2 Some Properties of Trees

3-3 Pendant Vertices in a Tree

3-4 Distance and Centers in a Tree

3-5 Rooted and Binary Trees

3-6 On Counting Trees

3-7 Spanning Trees

3-8 Fundamental Circuits

3-9 Finding All Spanning Trees of a Graph

3-10 Spanning Trees in a Weighted Graph

Summary

References

Problems

4 CUT-SETS AND CUT-VERTICES

4-1 Cut-Sets

4-2 Some Properties of a Cut-Set

4-3 All Cut-Sets in a Graph

4-4 Fundamental Circuits and Cut-Sets

4-5 Connectivity and Separability

4-6 Network Flows

4-7 1-Isomorphism

4-8 2-Isomorphism

Summary

References

Problems

5 PLANAR AND DUAL GRAPHS

5-1 Combinatorial Vs. Geometric Graphs

5-2 Planar Graphs

5-3 Kuratowski’s Two Graphs

5-4 Different Representations of a Planar Graph

5-5 Detection of Planarity

5-6 Geometric Dual

5-7 Combinatorial Dual

5-8 More on Criteria of Planarity

5-9 Thickness and Crossings

Summary

References

Problems

6 VECTOR SPACES OF A GRAPH

6-1 Sets with One Operation

6-2 Sets with Two Operations

6-3 Modular Arithmetic and Galois Fields

6-4 Vectors and Vector Spaces

6-5 Vector Space Associated with a Graph

6-6 Basis Vectors of a Graph

6-7 Circuit and Cut-Set Subspaces

6-8 Orthogonal Vectors and Spaces

6-9 Intersection and Join of W and Ws

Summary

References

Problems

7 MATRIX REPRESENTATION OF GRAPHS

7-1 Incidence Matrix

7-2 Submatrices of A(G)

7-3 Circuit Matrix

7-4 Fundamental Circuit Matrix and Rank of B

7-5 An Application to a Switching Network

7-6 Cut-Set Matrix

7-7 Relationships among Af

, Bf

, and Cf

7-8 Path Matrix

7-9 Adjacency Matrix

Summary

References

Problems

8 COLORING, COVERING, AND PARTITIONING

8-1 Chromatic Number

8-2 Chromatic Partitioning

8-3 Chromatic Polynomial

8-4 Matchings

8-5 Coverings

8-6 The Four Color Problem

Summary

References

Problems

9 DIRECTED GRAPHS

9-1 What Is a Directed Graph?

9-2 Some Types of Digraphs

9-3 Digraphs and Binary Relations

9-4 Directed Paths and Connectedness

9-5 Euler Digraphs

9-6 Trees with Directed Edges

9-7 Fundamental Circuits in Digraphs

9-8 Matrices A, B, and C of Digraphs

9-9 Adjacency Matrix of a Digraph

9-10 Paired Comparisons and Tournaments

9-11 Acyclic Digraphs and Decyclization

Summary

References

Problems

10 ENUMERATION OF GRAPHS

10-1 Types of Enumeration

10-2 Counting Labeled Trees

10-3 Counting Unlabeled Trees

10-4 Pólya’s Counting Theorem

10-5 Graph Enumeration With Pólya’s Theorem

Summary

References

Problems

11 GRAPH THEORETIC ALGORITHMS AND COMPUTER

PROGRAMS

11-1 Algorithms

11-2 Input: Computer Representation of a Graph

11-3 The Output

11-4 Some Basic Algorithms

Algorithm 1: Connectedness and Components

Algorithm 2: A Spanning Tree

Algorithm 3: A Set of Fundamental Circuits

Algorithm 4: Cut-Vertices and Separability

Algorithm 5: Directed Circuits

11-5 Shortest-Path Algorithms

Algorithm 6: Shortest Path from a Specified Vertex to Another

Specified Vertex

Algorithm 7: Shortest Path between All Pairs of Vertices

11-6 Depth-First Search on a Graph

Algorithm 8: Planarity Testing

11-7 Algorithm 9: Isomorphism

11-8 Other Graph-Theoretic Algorithms

11-9 Performance of Graph-Theoretic Algorithms

11-10 Graph-Theoretic Computer Languages

Summary

References

Problems

Appendix of Programs

12 GRAPHS IN SWITCHING AND CODING THEORY

12-1 Contact Networks

12-2 Analysis of Contact Networks

12-3 Synthesis of Contact Networks

12-4 Sequential Switching Networks

12-5 Unit Cube and Its Graph

12-6 Graphs in Coding Theory

Summary

References

13 ELECTRICAL NETWORK ANALYSIS BY GRAPH THEORY

13-1 What Is an Electrical Network?

13-2 Kirchhof’s Current and Voltage Laws

13-3 Loop Currents and Node Voltages

13-4 RLC Networks with Independent Sources: Nodal Analysis

13-5 RLC Networks with Independent Sources: Loop Analysis

13-6 General Lumped, Linear, Fixed Networks

Summary

References

Problems

14 GRAPH THEORY IN OPERATIONS RESEARCH

14-1 Transport Networks

14-2 Extensions of Max-Flow Min-Cut Theorem

14-3 Minimal Cost flows

14-4 The Multicommodity Flow

14-5 Further Applications

14-6 More on Flow Problems

14-7 Activity Networks in Project Planning

14-8 Analysis of an Activity Network

14-9 Further Comments on Activity Networks

14-10 Graphs in Game Theory

Summary

References

15 SURVEY OF OTHER APPLICATIONS

15-1 Signal-Flow Graphs

15-2 Graphs in Markov Processes

15-3 Graphs in Computer Programming

15-4 Graphs in Chemistry

15-5 Miscellaneous Applications

Appendix A BINET-CAUCHY THEOREM

Appendix B NULLITY OF A MATRIX AND SYLVESTER’S LAW

INDEX

PREFACE

The last two decades have witnessed an upsurge of interest and activity in

graph theory, particularly among applied mathematicians and engineers. Clear

evidence of this is to be found in an unprecedented growth in the number of

papers and books being published in the field. In 1957 there was exactly one

book on the subject (namely, König’s Théorie der Endlichen und Unendlichen

Graphen). Now, sixteen years later, there are over two dozen textbooks on graph

theory, and almost an equal number of proceedings of various seminars and

conferences.

Each book has its own strength and points of emphasis, depending on the axe

(or the pen) the author has to grind. I have emphasized the computational and

algorithmic aspects of graphs. This emphasis arises from the experience and

conviction that whenever graph theory is applied to solving any practical

problem (be it in electrical network analysis, in circuit layout, in data structures,

in operations research, or in social sciences), it almost always leads to large

graphs—graphs that are virtually impossible to analyze without the aid of the

computer. An engineer often finds that those real-life problems that can be

modeled into graphs small enough to be worked on by hand are also small

enough to be solved by means other than graph theory. (In this respect graph

theory is different from college algebra, elementary calculus, or complex

variables.) In fact, the high-speed digital computer is one of the reasons for the

recent growth of interest in graph theory.

Convinced that a student of applied graph theory must learn to enlist the help

of a digital computer for handling large graphs, I have emphasized algorithms

and their efficiencies. In proving theorems, constructive proofs have been given

preference over nonconstructive existence proofs. Chapter 11, the largest in the

book, is devoted entirely to computational aspects of graph theory, including

graph-theoretic algorithms and samples of several tested computer programs for

solving problems on graphs. I believe this approach has not been used in any of

the earlier books on graph theory. The material covered in Chapter 11 and in

many sections from other chapters is appearing for the first time in any textbook.

Yet the applied and algorithmic aspect of this book has not been allowed to

spoil the rigor and mathematical elegance of graph theory. Indeed, the book

contains enough material for a course in “pure” graph theory. The book has been

made as much self-contained as was possible.

The level of presentation is appropriate for advanced undergraduate and first￾year graduate students in all disciplines requiring graph theory. The book is

organized so that the first half (Chapters 1 through 9) serves as essential and

introductory material on graph theory. This portion requires no special

background, except some elementary concepts from set theory and matrix

algebra and, of course, a certain amount of mathematical maturity. Although the

illustrations of applications are interwoven with the theory even in this portion,

the examples selected are short and mostly of the nature of puzzles and games.

This is done so that a student in almost any field can read and grasp the first half.

The second half of the book is more advanced, and different chapters require

different backgrounds as they deal with applications to nontrivial, real-world,

complex problems in different fields. Keeping this in mind, Chapters 10 through

15 have been made independent of each other. One could study a later chapter

without going through the earlier ones, provided the first nine chapters have

been covered.

Since there is more material here than what can be covered in a one-semester

course, it is suggested that the contents be tailored to suit the requirements of the

students in different disciplines, for example:

1. Electrical Engineering: Chapters 1–9, and 11, 12, and 13.

2. Computer Science: Chapters 1–9, 11, 12, and parts of 10 and 15.

3. Operations Research: Chapters 1–9, and 11, 14, and parts of 15.

4. Applied Mathematics: Chapters 1–11 and parts of 15.

5. Introductory “pure” graph theory: Chapters 1–10.

In fact, the book grew out of a number of such courses and lecture-series

given by the author at the Jet Propulsion Laboratory, California State University

at Los Angeles, the Indian Institute of Technology at Kanpur, and the University

of Illinois at Urbana-Champaign.

ACKNOWLEDGMENTS

It is a pleasure to acknowledge the help I have received from different

individuals and institutions. I am particularly indebted to Mr. David K. Rubin, a

dear friend and former colleague at the Jet Propulsion Laboratory; Mr. Mateti

Prabhaker, a former graduate student of mine at the Indian Institute of

Technology, Kanpur; and Professor Jurg Nievergelt of the University of Illinois

at Urbana-Champaign for having read the entire manuscript and made numerous

suggestions for improvements throughout the book.

Other friends, colleagues, and students who read parts of the manuscript and

made helpful suggestions are: Professor Harry Lass and Mr. Marvin Perlman of

the Jet Propulsion Laboratory, Professor Nandlal Jhunjhunwala of California

State University at Los Angeles, Dr. George Shuraym of Texas Instruments, Mr.

Jean A, DeBeule of Xerox Data Systems, Mr. Nicholas Karpov of Bell &

Howell, Professor C. L. Liu of the University of Illinois at Urbana-Champaign,

Messrs. M. S. Krishnamoorthy, K. G. Ramakrishnan, and Professors C. R.

Muthukrishnan and S. K. Basu of the Indian Institute of Technology at Kanpur.

I am also grateful to the late Professor George E. Forsythe of Stanford

University for his encouragement at the very outset of this project.

Support in writing this book was received from the Jet Propulsion Laboratory,

the Indian Institute of Technology at Kanpur, and the Computer Science

Department of the University of Illinois at Urbana-Champaign.

Just as one does not thank himself, expressing gratitude to one’s wife in public

is not a Hindu custom. For the wife is considered a part of the husband, and her

coauthorship is tacitly assumed in any book her husband writes. There is little

doubt that without Kiran’s help this book would not have been possible.

NARSINGH DEO

Kanpur