| |
| |
| 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 | |