Graphs Theory and Applications

Jean-Claude Fournier is Professor at the University of Paris 12, France, and is a member of the Unite Mixte de Recherche Combinatoire et Optimisation (University of Paris 6 and CNRS) founded by Claude Berge.

• Introduction 17Chapter 1. Basic Concepts 211.1 The origin of the graph concept 211.2 Definition of graphs 241.3 Subgraphs 281.4 Paths and cycles 291.5 Degrees 331.6 Connectedness 351.7 Bipartite graphs 361.8 Algorithmic aspects 371.9 Exercises 41Chapter 2. Trees 452.1 Definitions and properties 452.2 Spanning trees 492.3 Application: minimum spanning tree problem 542.4 Connectivity 592.5 Exercises 66Chapter 3. Colorings 713.1 Coloring problems 713.2 Edge coloring 713.3 Algorithmic aspects 733.4 The timetabling problem 753.5 Exercises 81Chapter 4. Directed Graphs 834.1 Definitions and basic concepts 834.2 Acyclic digraphs 904.3 Arborescences 924.4 Exercises 95Chapter 5. Search Algorithms 975.1 Depth-first search of an arborescence 975.2 Optimization of a sequence of decisions 1035.3 Depth-first search of a digraph 1095.4 Exercises 117Chapter 6. Optimal Paths 1196.1 Distances and shortest paths problems 1196.2 Case of non-weighted digraphs: breadth-first search 1206.3 Digraphs without circuits 1256.4 Application to scheduling 1286.5 Positive lengths 1346.6 Other cases 1426.7 Exercises 143Chapter 7. Matchings 1497.1 Matchings and alternating paths 1497.2 Matchings in bipartite graphs 1527.3 Assignment problem 1567.4 Optimal assignment problem 1647.5 Exercises 171Chapter 8. Flows 1738.1 Flows in transportation networks 1738.2 The max-flow min-cut theorem 1778.3 Maximum flow algorithm 1808.4 Flow with stocks and demands 1888.5 Revisiting theorems 1918.6 Exercises 194Chapter 9. Euler Tours 1979.1 Euler trails and tours 1979.2 Algorithms 2019.3 The Chinese postman problem 2079.4 Exercises 212Chapter 10. Hamilton Cycles 21510.1 Hamilton cycles 21510.2 The traveling salesman problem 21810.3 Approximation of a difficult problem 22010.4 Approximation of themetric TSP 22310.5 Exercises 234Chapter 11. Planar Representations 23711.1 Planar graphs 23711.2 Other graph representations 24211.3 Exercises 244Chapter 12. Problems with Comments 24712.1 Problem 1: A proof of k-connectivity 24712.2 Problem2: An application to compiler theory 24912.3 Problem3: Kernel of a digraph 25112.4 Problem 4: Perfect matching in a regular bipartite graph 25312.5 Problem5: Birkhoff-Von Neumann’s theorem 25412.6 Problem 6: Matchings and tilings 25612.7 Problem7: Strip mining 258Appendix A. Expression of Algorithms 261Appendix B. Bases of Complexity Theory 267Bibliography 277Index 279