简介
"This is a textbook on graph theory, especially suitable for computer scientists but also suitable for mathematicians with an interest in computational complexity. Although it introduces most of the classical concepts of pure and applied graph theory (spanning trees, connectivity, genus, colourability, flows in networks, matchings and traversals) and covers many of the major classical theorems, the emphasis is on algorithms and thier complexity: which graph problems have known efficient solutions and which are intractable. For the intractable problems a number of efficient approximation algorithms are included with known performance bounds. Informal use is made of a PASCAL-like programming language to describe the algorithms. A number of exercises and outlines of solutions are included to extend and motivate the material of the text."-- Book cover.
目录
Preface p. xi
Introducing graphs and algorithmic complexity p. 1
Introducing graphs p. 1
Introducing algorithmic complexity p. 8
Introducing data structures and depth-first searching p. 16
Adjacency matrices and adjacency lists p. 17
Depth-first searching p. 20
Two linear-time algorithms p. 24
Summary and references p. 32
Exercises p. 33
Spanning-trees, branchings and connectivity p. 39
Spanning-trees and branchings p. 39
Optimum weight spanning-trees p. 40
Optimum branchings p. 42
Enumeration of spanning-trees p. 49
Circuits, cut-sets and connectivity p. 54
Fundamental circuits of a graph p. 54
Fundamental cut-sets of a graph p. 57
Connectivity p. 60
Summary and references p. 62
Exercises p. 63
Planar graphs p. 67
Basic properties of planar graphs p. 67
Genus, crossing-number and thickness p. 71
Characterisations of planarity p. 75
Dual graphs p. 81
A planarity testing algorithm p. 85
Summary and references p. 92
Exercises p. 93
Networks and flows p. 96
Networks and flows p. 96
Maximising the flow in a network p. 98
Menger's theorems and connectivity p. 106
A minimum-cost flow algorithm p. 111
Summary and references p. 118
Exercises p. 120
Matchings p. 125
Definitions p. 125
Maximum-cardinality matchings p. 126
Perfect matchings p. 134
Maximum-weight matchings p. 136
Summary and references p. 147
Exercises p. 148
Eulerian and Hamiltonian tours p. 153
Eulerian paths and circuits p. 153
Eulerian graphs p. 155
Finding Eulerian circuits p. 156
Postman problems p. 161
Counting Eulerian circuits p. 162
The Chinese postman problem for undirected graphs p. 163
The Chinese postman problem for digraphs p. 165
Hamiltonian tours p. 169
Some elementary existence theorems p. 169
Finding all Hamiltonian tours by matricial products p. 173
The travelling salesman problem p. 175
2-factors of a graph p. 182
Summary and references p. 184
Exercises p. 185
Colouring graphs p. 189
Dominating sets, independence and cliques p. 189
Colouring graphs p. 195
Edge-colouring p. 195
Vertex-colouring p. 198
Chromatic polynomials p. 201
Face-colourings of embedded graphs p. 204
The five-colour theorem p. 204
The four-colour theorem p. 207
Summary and references p. 210
Exercises p. 212
Graph problems and intractability p. 217
Introduction to NP-completeness p. 217
The classes P and NP p. 217
NP-completeness and Cook's theorem p. 222
NP-complete graph problems p. 227
Problems of vertex cover, independent set and clique p. 227
Problems of Hamiltonian paths and circuits and the travelling salesman problem p. 229
Problems concerning the colouring of graphs p. 235
Concluding comments p. 241
Summary and references p. 244
Exercises p. 245
On linear programming p. 249
Author index p. 254
Subject index p. 256
Introducing graphs and algorithmic complexity p. 1
Introducing graphs p. 1
Introducing algorithmic complexity p. 8
Introducing data structures and depth-first searching p. 16
Adjacency matrices and adjacency lists p. 17
Depth-first searching p. 20
Two linear-time algorithms p. 24
Summary and references p. 32
Exercises p. 33
Spanning-trees, branchings and connectivity p. 39
Spanning-trees and branchings p. 39
Optimum weight spanning-trees p. 40
Optimum branchings p. 42
Enumeration of spanning-trees p. 49
Circuits, cut-sets and connectivity p. 54
Fundamental circuits of a graph p. 54
Fundamental cut-sets of a graph p. 57
Connectivity p. 60
Summary and references p. 62
Exercises p. 63
Planar graphs p. 67
Basic properties of planar graphs p. 67
Genus, crossing-number and thickness p. 71
Characterisations of planarity p. 75
Dual graphs p. 81
A planarity testing algorithm p. 85
Summary and references p. 92
Exercises p. 93
Networks and flows p. 96
Networks and flows p. 96
Maximising the flow in a network p. 98
Menger's theorems and connectivity p. 106
A minimum-cost flow algorithm p. 111
Summary and references p. 118
Exercises p. 120
Matchings p. 125
Definitions p. 125
Maximum-cardinality matchings p. 126
Perfect matchings p. 134
Maximum-weight matchings p. 136
Summary and references p. 147
Exercises p. 148
Eulerian and Hamiltonian tours p. 153
Eulerian paths and circuits p. 153
Eulerian graphs p. 155
Finding Eulerian circuits p. 156
Postman problems p. 161
Counting Eulerian circuits p. 162
The Chinese postman problem for undirected graphs p. 163
The Chinese postman problem for digraphs p. 165
Hamiltonian tours p. 169
Some elementary existence theorems p. 169
Finding all Hamiltonian tours by matricial products p. 173
The travelling salesman problem p. 175
2-factors of a graph p. 182
Summary and references p. 184
Exercises p. 185
Colouring graphs p. 189
Dominating sets, independence and cliques p. 189
Colouring graphs p. 195
Edge-colouring p. 195
Vertex-colouring p. 198
Chromatic polynomials p. 201
Face-colourings of embedded graphs p. 204
The five-colour theorem p. 204
The four-colour theorem p. 207
Summary and references p. 210
Exercises p. 212
Graph problems and intractability p. 217
Introduction to NP-completeness p. 217
The classes P and NP p. 217
NP-completeness and Cook's theorem p. 222
NP-complete graph problems p. 227
Problems of vertex cover, independent set and clique p. 227
Problems of Hamiltonian paths and circuits and the travelling salesman problem p. 229
Problems concerning the colouring of graphs p. 235
Concluding comments p. 241
Summary and references p. 244
Exercises p. 245
On linear programming p. 249
Author index p. 254
Subject index p. 256
- 名称
- 类型
- 大小
光盘服务联系方式: 020-38250260 客服QQ：4006604884
云图客服：
用户发送的提问，这种方式就需要有位在线客服来回答用户的问题，这种 就属于对话式的,问题是这种提问是否需要用户登录才能提问
Video Player
×
Audio Player
×
pdf Player
×
