Algorithmic Graph Theory

Preface (xi)
1 Introducing graphs and alprltlunle oomplexlty 1
I.I Introducing graphs 1
1.2 Introducing algorithmic complexity 8
1.3 Introducing data structures and depth-first searching 16
1.3.1. Adjacency matrices and adjacency lists 17
1.3.2. Depth-first searching 20
1.3.3. Two linear-time algorithms 24
1.4 Summary and references 32
Exercises 33
2 Spanning-trees, branddnp and connectivity 39
2.1 Spanning-trees and branchings 39
2.1.1. Optimum weight spanning-trees 40
2.1.2. Optimum branchinp 42
2.1.3. Enumeration of spanning-tres 49
2.2 Circuits, cut-sets and connectivity S4
2.21. Fundamental circuits of a graph S4
2.2.2. Fundamental cut-sets of a graph S7
2.2.3. Connectivity 60
2.3 Summary and references 62
Exercises 63
3 Planar graphs 67
3.1 Basic properties of planar graphs 67
3.2 Genus, crossing-number and thickness 71
3.3 Characterisations of planarity 1S
3.3.1. Dual graphs 81
3.4 A planarity testing algorithm 8S
3.S Summary and references 92
Exercises
4 Networks and flows 96
4.1 Networks and flows 96
4.2 Maximising the flow in a network 98
4.3 Menger's theorems and connectivity 106
4.4 A minimum-cost flow algorithm 111
4.5 Summary and references 118
Exercises 120
5 Matchings
125
5.1 Definitions
125
5.2 Maximum-cardinality matchings 126
5.2.1. Perfect matchings 134
5.3 Maximum-weight matchings 136
5.4 Summary and references 147
Exercises 148
6 Eulerlan and Hamiltonian tours 153
6.1 Eulerian paths and circuits 153
6.1.1. Eulerian graphs 155
6.1.2. Finding Eulerian circuits 156
6.2 Postman problems 161
6.2.1. Counting Eulerian circuits 162
6.2.2. The Chinese postman problem for undirected graphs 163
6.2.3. The Chinese postman problem for digraphs 165
6.3 Hamiltonian tours 169
6.3.1. Some elementary existence theorems 169
6.3.2. Finding all Hamiltonian tours by matricial products 173
6.3.3, The travelling salesman prob1em 175
6.3.4, 2-factors of a graph 182
6.4 Summary and references 184
Exercises 185
7 Colourlq araphs 189
7.1 Dominating sets, independence and cliques 189
7.2 Colouring graphs 195
7.2.1. Edge-colouring 195
7.2.2. Vertex-colouring 198
7 .2.3, Chromatic polynomials 201
7.3 Face-colourings of embedded graphs 204
7,3.1, The five-colour theorem 204
7,3.2. The four-colour theorem 2'11
7.4 Summary and references 210
Exercises 212
8 Graph problems and lntradablllty 217
8.1 Introduction to NP-completeness 217
Content, ix
8.1.1. The classes P and NP 217
8.1.2. NP-completeness and Cook's theorem 222
8.2 NP-complete paph problems 227
8.2.1. Problems of vertex cover, independent set and clique 227
8.2.2. Problems of Hamiltonian paths and circuits and the
travelling salesman problem 229
8.2.3. Problems concerning the colouring of paphs 235
8.3 Concluding comments 241
8.4 Summary and references 244
Exercises 245
Appendix: On linear prognmuning 249
Author index 254
Subject index 256