Graph Theory with Applications to Engineering and Computer ...

1 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.

2 | 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 D46 2016 | DDC 511/.5 dc23 LC record available at Manufactured in the United States by RR Donnelley 80793201 2016. 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.

3 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 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.

5 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.

6 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.

7 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.

8 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.

9 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 .

10 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.