Theory and Application of Graphs

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.