Graph Theory: An Introduction to Proofs, Algorithms, and Applications

Description

Graph Theory: An Introduction to Proofs, Algorithms, and Applications Graph theory is the study of interactions, conflicts, and connections. The relationship between collections of discrete objects can inform us about the overall network in which they reside, and graph theory can provide an avenue for analysis. This text, for the first undergraduate course, will explore major topics in graph theory from both a theoretical and applied viewpoint. Topics will progress from understanding basic terminology, to addressing computational questions, and finally ending with broad theoretical results. Examples and exercises will guide the reader through this progression, with particular care in strengthening proof techniques and written mathematical explanations. Current applications and exploratory exercises are provided to further the reader’s mathematical reasoning and understanding of the relevance of graph theory to the modern world. Features The first chapter introduces graph terminology, mathematical modeling using graphs, and a review of proof techniques featured throughout the book The second chapter investigates three major route problems: eulerian circuits, hamiltonian cycles, and shortest paths. The third chapter focuses entirely on trees – terminology, applications, and theory. Four additional chapters focus around a major graph concept: connectivity, matching, coloring, and planarity. Each chapter brings in a modern application or approach. Hints and Solutions to selected exercises provided at the back of the book. Author Karin R. Saoub is an Associate Professor of Mathematics at Roanoke College in Salem, Virginia. She earned her PhD in mathematics from Arizona State University and BA from Wellesley College. Her research focuses on graph coloring and on-line algorithms applied to tolerance graphs. She is also the author of A Tour Through Graph Theory, published by CRC Press. Cover Half Title Series Page Title Page Copyright Page Dedication Contents Preface 1. Graph Models, Terminology, and Proofs 1.1. Tournaments 1.2. Introduction to Graph Models and Terminology 1.2.1. Digraphs 1.2.2. Weighted Graphs 1.2.3. Complete Graphs 1.2.4. Graph Complements 1.2.5. Bipartite Graphs 1.2.6. Graph Combinations 1.3. Isomorphisms 1.4. Matrix Representation 1.5. Proof Techniques 1.5.1. Direct Proofs 1.5.2. Indirect Proofs 1.5.3. Mathematical Induction 1.6. Degree Sequence 1.7. Tournaments Revisited 1.7.1. Score Sequence 1.7.2. Matrix Representation 1.8. Exercises 2. Graph Routes 2.1. Eulerian Circuits 2.1.1. Konigsberg Bridge Problem 2.1.2. Touring a Graph 2.1.3. Eulerian Graphs 2.1.4. Algorithms 2.1.5. Applications 2.2. Hamiltonian Cycles 2.2.1. The Traveling Salesman Problem 2.2.2. Tournaments Revisited 2.3. Shortest Paths 2.3.1. Dijkstra's Algorithm 2.3.2. Walks Using Matrices 2.3.3. Distance, Diameter, and Radius 2.4. Exercises 3. Trees 3.1. Spanning Trees 3.1.1. Minimum Spanning Trees 3.2. Tree Properties 3.2.1. Tree Enumeration 3.3. Rooted Trees 3.3.1. Depth-First Search Tree 3.3.2. Breadth-First Search Tree 3.3.3. Mazes 3.4. Additional Applications 3.4.1. Traveling Salesman Revisited 3.4.2. Decision Trees 3.4.3. Chemical Graph Theory 3.5. Exercises 4. Connectivity and Flow 4.1. Connectivity Measures 4.1.1. k-Connected 4.1.2. k-Edge-Connected 4.1.3. Whitney's Theorem 4.2. Connectivity and Paths 4.2.1. Menger's Theorem 4.3. 2-Connected Graphs 4.3.1. 2-Edge-Connected 4.4. Network Flow 4.5. Centrality Measures 4.6. Exercises 5. Matching and Factors 5.1. Matching in Bipartite Graphs 5.1.1. Augmenting Paths and Vertex Covers 5.1.2. Hall's Theorem Revisited 5.2. Matching in General Graphs 5.2.1. Edmonds' Blossom Algorithm 5.2.2. Chinese Postman Problem 5.3. Stable Matching 5.3.1. Unacceptable Partners 5.3.2. Stable Roommates 5.4. Factors 5.5. Exercises 6. Graph Coloring 6.1. Four Color Theorem 6.2. Vertex Coloring 6.2.1. Coloring Strategies 6.2.2. General Results 6.3. Edge Coloring 6.3.1. 1-Factorizations Revisited 6.3.2. Ramsey Numbers 6.4. Coloring Variations 6.4.1. On-line Coloring 6.4.2. Proof of Brooks' Theorem 6.4.3. Weighted Coloring 6.4.4. List Coloring 6.5. Exercises 7. Planarity 7.1. Kuratowski's Theorem 7.1.1. Euler's Formula 7.1.2. Cycle-Chord Method 7.1.3. Proof of Kuratowski's Theorem 7.2. Graph Coloring Revisited 7.3. Edge-Crossing 7.3.1. Thickness 7.4. Exercises Appendix A. Set Theory B. Functions C. Matrix Operations D. Algorithm Efficiency E. Pseudocode Selected Hints and Solutions Bibliography Image Credits Index