Theory and Application of Graphs
==========================================================================
Preface
In the spectrum of mathematics, graph theory which
studies a mathematical 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 developments 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 impossible 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 materials 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 difficult, 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 special 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 applied, 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, together 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 to understand the given materials. To explore the mathematical nature of graph theory
better, we will specially stress the equivalence of some classical results, such as the max-flow min-cut theorem of Ford and
Fulkerson, Menger's theorem, Hall's theorem, Tutte's theorem and K\"onig'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 computer 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 (or 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 text for a senior and first-year postgraduate 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
( xujm@ustc.edu.cn )
December 2002
|
