A Tour through Graph Theory

Contents......Page 3
Preface......Page 6
Konigsberg Bridge Problem......Page 9
Introduction to Graph Models......Page 10
Touring a Graph......Page 14
Eulerian Circuit Algorithms......Page 20
Eulerization......Page 27
Exercises......Page 35
Hamiltonian Cycles......Page 43
Conditions for Existence......Page 44
Traveling Salesman Problem......Page 49
Digraphs......Page 71
Exercises......Page 80
Shortest Paths......Page 89
Project Scheduling......Page 101
Exercises......Page 111
Trees......Page 117
Spanning Trees......Page 121
Shortest Networks......Page 138
Traveling Salesman Problem Revisited......Page 148
Exercises......Page 152
Matching......Page 159
Bipartite Graphs......Page 160
Matching Terminology and Strategies......Page 162
Stable Marriages......Page 176
Matchings in Non-Bipartite Graphs......Page 184
Exercises......Page 188
Four Color Theorem......Page 196
Coloring Bounds......Page 199
Coloring Strategies......Page 203
Perfect Graphs......Page 214
Weighted Coloring......Page 223
Exercises......Page 228
Algorithm Complexity......Page 234
Graph Isomorphism......Page 239
Tournaments......Page 243
Flow and Capacity......Page 252
RootedTrees......Page 263
Planarity......Page 272
Edge-Coloring......Page 281
Appendix......Page 292
Chapter 1: Eulerian Tours......Page 295
Chapter 2: Hamiltonian Cycles......Page 296
Chapter 4: Trees and Networks......Page 297
Chapter 7: Additional Topics......Page 298
Biblio......Page 300
Index......Page 303