| |
| |
Preface | |
| |
| |
| |
Introducing graphs and algorithmic complexity | |
| |
| |
| |
Introducing graphs | |
| |
| |
| |
Introducing algorithmic complexity | |
| |
| |
| |
Introducing data structures and depth-first searching | |
| |
| |
| |
Adjacency matrices and adjacency lists | |
| |
| |
| |
Depth-first searching | |
| |
| |
| |
Two linear-time algorithms | |
| |
| |
| |
Summary and references | |
| |
| |
Exercises | |
| |
| |
| |
Spanning-trees, branchings and connectivity | |
| |
| |
| |
Spanning-trees and branchings | |
| |
| |
| |
Optimum weight spanning-trees | |
| |
| |
| |
Optimum branchings | |
| |
| |
| |
Enumeration of spanning-trees | |
| |
| |
| |
Circuits, cut-sets and connectivity | |
| |
| |
| |
Fundamental circuits of a graph | |
| |
| |
| |
Fundamental cut-sets of a graph | |
| |
| |
| |
Connectivity | |
| |
| |
| |
Summary and references | |
| |
| |
Exercises | |
| |
| |
| |
Planar graphs | |
| |
| |
| |
Basic properties of planar graphs | |
| |
| |
| |
Genus, crossing-number and thickness | |
| |
| |
| |
Characterisations of planarity | |
| |
| |
| |
Dual graphs | |
| |
| |
| |
A planarity testing algorithm | |
| |
| |
| |
Summary and references | |
| |
| |
Exercises | |
| |
| |
| |
Networks and flows | |
| |
| |
| |
Networks and flows | |
| |
| |
| |
Maximising the flow in a network | |
| |
| |
| |
Menger's theorems and connectivity | |
| |
| |
| |
A minimum-cost flow algorithm | |
| |
| |
| |
Summary and references | |
| |
| |
Exercises | |
| |
| |
| |
Matchings | |
| |
| |
| |
Definitions | |
| |
| |
| |
Maximum-cardinality matchings | |
| |
| |
| |
Perfect matchings | |
| |
| |
| |
Maximum-weight matchings | |
| |
| |
| |
Summary and references | |
| |
| |
Exercises | |
| |
| |
| |
Eulerian and Hamiltonian tours | |
| |
| |
| |
Eulerian paths and circuits | |
| |
| |
| |
Eulerian graphs | |
| |
| |
| |
Finding Eulerian circuits | |
| |
| |
| |
Postman problems | |
| |
| |
| |
Counting Eulerian circuits | |
| |
| |
| |
The Chinese postman problem for undirected graphs | |
| |
| |
| |
The Chinese postman problem for digraphs | |
| |
| |
| |
Hamiltonian tours | |
| |
| |
| |
Some elementary existence theorems | |
| |
| |
| |
Finding all Hamiltonian tours by matricial products | |
| |
| |
| |
The travelling salesman problem | |
| |
| |
| |
2-factors of a graph | |
| |
| |
| |
Summary and references | |
| |
| |
Exercises | |
| |
| |
| |
Colouring graphs | |
| |
| |
| |
Dominating sets, independence and cliques | |
| |
| |
| |
Colouring graphs | |
| |
| |
| |
Edge-colouring | |
| |
| |
| |
Vertex-colouring | |
| |
| |
| |
Chromatic polynomials | |
| |
| |
| |
Face-colourings of embedded graphs | |
| |
| |
| |
The five-colour theorem | |
| |
| |
| |
The four-colour theorem | |
| |
| |
| |
Summary and references | |
| |
| |
Exercises | |
| |
| |
| |
Graph problems and intractability | |
| |
| |
| |
Introduction to NP-completeness | |
| |
| |
| |
The classes P and NP | |
| |
| |
| |
NP-completeness and Cook's theorem | |
| |
| |
| |
NP-complete graph problems | |
| |
| |
| |
Problems of vertex cover, independent set and clique | |
| |
| |
| |
Problems of Hamiltonian paths and circuits and the travelling salesman problem | |
| |
| |
| |
Problems concerning the colouring of graphs | |
| |
| |
| |
Concluding comments | |
| |
| |
| |
Summary and references | |
| |
| |
Exercises | |
| |
| |
| |
On linear programming | |
| |
| |
Author index | |
| |
| |
Subject index | |