Introduction to Graph Theory

DESCRIPTION This innovative text introduces a new way of teaching graph theory. Graph theory has applications in many areas of natural science, social science, and engineering. Therefore, a class in this course may consist of students from different backgrounds. Furthermore, a graph theory course can be taught by a mathematics, computer science, or an engineering department. However, such a course is typically taught by a mathematics department with a diversity of students. Therefore, it is important that a course in graph theory must present a balance of theoretical concepts as well as their relevant applications. The approach that we have taken in this book is a culmination of years of experience. Our main objective is to make the learning of graph theory easier and enjoyable. Through using this text, we want to provide students with a solid foundation of theoretical concepts and their applications. Introduction to Graph Theory shows why theory is important and how theory connects with applications. This book is written exclusively for students new to graph theory. The language used is simple and thus, conducive to learning the profound concepts present in graph theory. Sometimes, mathematical proofs of theorems and corollaries include extra details so that weak as well as strong students can grasp the fundamental concepts. KEY FEATURES Learning Objectives offer an outline of the concepts discussed in detail in the chapter. Remarks highlight important facts about the concepts introduced in the chapter. More than 400 visual diagrams, both extensive and exhaustive, illustrate difficult concepts. Numbered Examples illustrate the key concepts. Worked-Out Exercises is a set of fully worked-out exercises provided at the end of each chapter. Some Key Definitions and Some Key Highlights at the end of each chapter reinforce students understanding of the key concepts learnt. Exercises further reinforce learning and ensure that students have, in fact, learned the concepts presented in each chapter. Programming Exercises allow students to apply their coding skills in C++ and Java using the concepts learnt in the chapter. TABLE OF CONTENTS Preface About the Authors List of Symbols 1. Basic Properties of Graphs 2. Connectivity and Bipartite Graphs 3. Eulerian Graphs and Hamiltonian Graphs 4. Matrix Representation and Isomorphisms of Graphs 5. Graph Algorithms 6. Trees 7. Rooted Trees 8. Spanning Trees 9. Planar Graphs and Graph Coloring 10. Networks 11. Interval Graphs 12. Intersection Graphs Appendix A A Review of Basic Set Theory and Algorithms Appendix B Answers and Hints to Selected Exercises References Index