Theory and Application of Graphs Network Theory and Applications Valurne 10 Managing Editors: Ding-ZhuDu University ofMinnesota, U.S.A. Cauligi Raghavendra UniversityofSouthern Califorina, U.SA. Theory and Application of Graphs by Junming Xu Department of Mathematics U niversity of Science and Technology of China Hefei, Anhui, China Springer Science+ Business Media, LLC Library of Congress Cataloging-in-Publication CIP info or: Title: Theory and Application ofGraphs Author: Xu ISBN 978-1-4613-4670-8 ISBN 978-1-4419-8698-6 (e Book) DOI 10.1007/978-1-4419-8698-6 Copyright© 2003 by Springer Science+Business Media New York Originally published by Kluwer Academic Publishers in 2003 Softcover reprint of the bardeover 1st edition 2003 All rights reserved. No partoftbis publication may be reproduced, stored in a retrieval system or transmitted in any form or by any means, electronic, mechanical, photo-copying, microfilming, recording, or otherwise, without the prior written permission ofthe publisher, with the exception of any material supplied specifically for the purpose ofbeing entered and executed on a computer system, for exclusive use by the purchaser ofthe work. Permissions forbooks published in the USA: permj ssj ons@wkap CQJD Permissions for books published in Europe: [email protected] Printed on acid-Jree paper. Contents Preface vii 1 Basic Concepts of Graphs 1 1.1 Graph and Graphical Presentation 2 1.2 Graph Isomorphism . . . . 7 1.3 Vertex Degrees ....... . 14 1.4 Subgraphs and Operations . . 19 1.5 Walks, Paths and Connection 25 1.6 Distauces and Diameters . 32 1. 7 Circuits and Cycles . 38 1.8 Eulerian Graphs . . . . . 47 1.9 Hamiltonian Graphs ... 54 1.10 Matrix Presentation of Graphs 62 Applications 1.11 Exponents of Primitive Matrices 70 2 Trees and Graphie Spaces 79 2.1 Trees and Spanning Trees 80 2.2 Vector Spaces of Graphs . 88 2.3 Enumeration of Spanning Trees 100 Applications 2.4 The Minimum Connector Problem 107 2.5 The Shortest Path Problem .... 113 2.6 The Electrical Network Equations 122 3 Plane Graphs and Planar Graphs 127 3.1 PlaneGraphsand Euler's Formula 128 3.2 Kuratowski's Theorem 137 3.3 Dual Graphs . . . . . 143 Applications Contents VI 3.4 Regular Polyhedra . . . . . 148 3.5 Layout of Printed Circuits . 151 4 Flows and Connectivity 159 4.1 Network Flows .. 160 4.2 Menger's Theorem 165 4.3 Connectivity . . . 174 Applications 4.4 Design of Transport Schemes ..... 183 4.5 Design of Optimal Transport Schemes 191 4.6 The Chinese Postman Problem ... 197 4. 7 Construction of Squared Rectangles 204 5 Matchings and Independent Sets 211 5.1 Matchings 212 5.2 Independent Sets 227 Applications 5.3 The Personnel Assignment Problem 232 5.4 The Optimal Assignment Problem 241 5.5 The Travelling Salesman Problem . 250 6 Coloring Theory 257 6.1 Vertex Colorings 258 6.2 Edge Colarings . 265 Applications 6.3 The Four-Color Problem . 271 7 Graphs and Groups 279 7.1 Group Presentation of Graphs . 280 7.2 Transitive Graphs ...... . 285 7.3 Graphie Presentation of Groups . 294 Applications 301 7.4 Design of Interconnection Networks . 301 Bibliography 309 List of Symbols 323 Index 327 Preface In the spectrum of mathematics, graph theory which studies a mathe matical structure on a set of elements with a binary relation, as a recognized discipline, is a relative newcomer. In recent three decades the exciting and rapidly growing area of the subject abounds with new mathematical devel opments and significant applications to real-world problems. More and more colleges and universities have made it a required course for the senior or the beginning postgraduate students who are majoring in mathematics, computer science, electronics, scientific management and others. This book provides an introduction to graph theory for these students. The richness of theory and the wideness of applications make it impossi ble to include all topics in graph theory in a textbook for one semester. All materials presented in this book, however, I believe, are the most classical, fundamental, interesting and important. The method we deal with the mate rials is to particularly lay stress on digraphs, regarding undirected graphs as their special cases. My own experience from teaching out of the subject more than ten years at University of Science and Technology of China (USTC) shows that this treatment makes hardly the course di:fficult, but much more accords with the essence and the development trend of the subject. The book consists of seven chapters. Excepting that the first chapter contains the most basic concepts and results, each chapter presents one spe cial topic, including trees and graphic spaces, plane and planar graphs, flows and connectivity, matchings and independent sets, coloring theory, graphs and groups. These topics are treated in some depth, both theoretical and ap plied, with some suggestions for further reading. Every effort will be made to strengthen the mutual connections among these topics, with an aim to make the materials more systematic and cohesive. All theorems will be stated clearly, tagether with full and concise proofs, some of them are new. A number of examples and more than 350 figures are given to help the reader VIII Preface to understand the given materials. To explore the mathematical nature of graph theory better, we will specially stress the equivalence of some classi cal results, such as the max-flow min-cut theorem of Ford and Fulkerson, Menger's theorem, Hall's theorem, Tutte's theorem and König's theorem. Throughout this book the reader will see that graph theory has closed connection with other branches of mathematics, including linear algebra, matrix theory, group theory, combinatorics, combinatorial optimization and operation research, and wide applications to other subjects, including Com puter science, electronics, scientific management and so on. The applications carefully selected are arranged in the latter section(s) of each chapter. The aim of such arrangements is to conveniently choose these materials for some readers according to their interesting and available periods. Exercises at the end of each section, more than 500, from routine practice to challenging, are Supplements to the text. Some of them are very important results in graph theory. It is advisable for the reader to be familiar with the new definitions introduced in the exercises since they are useful for further study. The reader is also advised to do the exercises as many as he (o r she) can. The harder ones are indicated by bold type. The style of writing and of presentation of this book have be, to a great extent, influenced by Graph Theory with Applications, a popular textbook written by J. A. Bondy and U. S. R. Murty whom I am grateful to, from which some typical materials have been directly selected in this book. The book is developed from the textforasenior and first-year postgrad uate course in one semester at USTC. I thank the participants of the course for their great interest and stimulating comments. I would like to thank Teaching Affairs Division, Graduate School and Department of Mathematics at USTC for their support and encouragement. Many people have contributed, either directly or indirectly, to this book. I avail myself of this opportunity to particularly express my heartfelt gratitude to Qiao Li, Feng Tian, Yanpei Liu, Genghua Fan, Yongchuan Chen, Dingzhu Du and Shenggui Zhang for their continuous help and valuable suggestions. Finally, I would like to express my appreciation to my son, Keli Xu, for his very concrete help, and my wife, Jingxia Qiu, for her support, understanding and love, without which this work would have been impossible. Jun-Ming Xu ([email protected]) December 2002 Chapter 1 Basic Concepts of Graphs In many real-world situations, it is particularly convenient to describe the specified relationship between pairs of certain given objects by means of a diagram, in which points presents the objects and (directed or undirected) Iines the relationship between pairs of the objects. For example, a national traffic map describes a condition of the communication lines among cities in the country, where the points represent cities and the lines represent the highways or the railways joining pairs of cities. Notice that in such diagrams one is mainly interested in whether or not two given points are joined by a Iine; the manner in which they are joined is immaterial. A mathematical abstraction of situations of this type gives rise to the concept of a graph. In fact, a graph provides the natural structures from which to construct mathematical models that are appropriate to almost all fields of scientific (natural and social) inquiry. The underlying subject of study in these fields is some set of "objects" and one or more "relations" between the objects. In this chapter, we will introduce basic concepts of a graph used in the remaining parts of the book, including several special graphs, subgraphs of various types, walk, path, cycle, diameter, connection, Euler circuit, Rarnil ton cycle, adjacency and incidence matrices, as weil as the basic results closely related these concepts. At the end of this chapter we will present an appli cation of graphs to matrix theory. It should, for the beginner specially, be worth noting that most graph theorists use personalized terminology in their books, papers and lectures. Even the meaning of the word "graph" varies with different authors. We will adopt the most standard terminology and notation extensively used by most authors, with a subject index and a Iist of symbols in the end of the book.