Graphs, Networks and Algorithms (Algorithms and Computation in Mathematics)
Graphs, Networks and Algorithms (Algorithms and Computation in Mathematics)
ISBN: 9783540219057
出版社: Springer
出版年: 2004-11-29
页数: 611
定价: USD 79.95
装帧: Hardcover
内容简介
Preface to the Third Edition...................................VII
Preface to the Second Edition ................................. IX
Preface to the First Edition ................................... XI
1 Basic Graph Theory ....................................... 1
1.1 Graphs, subgraphsandfactors ........................... 2
1.2 Paths, cycles, connectedness, trees . . . . . . . . . . . . . . . . . . . . . . . . 5
1.3 Euler tours ............................................ 13
1.4 Hamiltonian cycles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
1.5 Planargraphs.......................................... 21
1.6 Digraphs .............................................. 25
1.7 An application: Tournaments and leagues . . . . . . . . . . . . . . . . . . 28
2 Algorithms and Complexity ............................... 33
2.1 Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
2.2 Representinggraphs .................................... 36
2.3 The algorithm of Hierholzer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
2.4 How to write down algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
2.5 The complexity of algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
2.6 Directedacyclicgraphs.................................. 46
2.7 NP-completeproblems .................................. 49
2.8 HCisNP-complete ..................................... 53
3 Shortest Paths ............................................. 59
3.1 Shortestpaths ......................................... 59
3.2 Finitemetric spaces .................................... 61
3.3 Breadth ?rst search and bipartite graphs . . . . . . . . . . . . . . . . . . 63
3.4 Shortestpathtrees ..................................... 68
3.5 Bellman’s equations and acyclic networks . . . . . . . . . . . . . . . . . . 70
XVI Contents
3.6 An application: Scheduling projects . . . . . . . . . . . . . . . . . . . . . . . 72
3.7 The algorithm of Dijkstra . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
3.8 An application: Train schedules . . . . . . . . . . . . . . . . . . . . . . . . . . 81
3.9 The algorithm of Floyd and Warshall . . . . . . . . . . . . . . . . . . . . . 84
3.10 Cycles of negative length . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
3.11 Path algebras . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90
4 Spanning Trees ............................................ 97
4.1 Treesandforests ....................................... 97
4.2 Incidence matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99
4.3 Minimal spanning trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104
4.4 The algorithms of Prim, Kruskal and Boruvka . . . . . . . . . . . . . 106
4.5 Maximal spanning trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113
4.6 Steiner trees ...........................................115
4.7 Spanning trees with restrictions . . . . . . . . . . . . . . . . . . . . . . . . . . 118
4.8 Arborescences and directed Euler tours . . . . . . . . . . . . . . . . . . . . 121
5 The Greedy Algorithm ....................................127
5.1 The greedy algorithm and matroids . . . . . . . . . . . . . . . . . . . . . . . 127
5.2 Characterizations of matroids . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129
5.3 Matroid duality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135
5.4 The greedy algorithm as an approximation method . . . . . . . . . 137
5.5 Minimization in independence systems . . . . . . . . . . . . . . . . . . . . 144
5.6 Accessible set systems...................................148
6Flows ......................................................153
6.1 The theoremsofFordandFulkerson ......................153
6.2 The algorithm of Edmonds and Karp . . . . . . . . . . . . . . . . . . . . . 159
6.3 Auxiliary networks and phases . . . . . . . . . . . . . . . . . . . . . . . . . . . 169
6.4 Constructingblocking?ows..............................176
6.5 Zero-one?ows .........................................185
6.6 The algorithm of Goldberg and Tarjan . . . . . . . . . . . . . . . . . . . . 189
7 Combinatorial Applications ................................209
7.1 Disjointpaths:Menger’s theorem.........................209
7.2 Matchings: K¨ onig’s theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 213
7.3 Partial transversals: The marriage theorem . . . . . . . . . . . . . . . . 218
7.4 Combinatorics of matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 223
7.5 Dissections: Dilworth’s theorem . . . . . . . . . . . . . . . . . . . . . . . . . . 227
7.6 Parallelisms: Baranyai’s theorem . . . . . . . . . . . . . . . . . . . . . . . . . 231
7.7 Supply and demand: The Gale-Ryser theorem. . . . . . . . . . . . . . 234
8 Connectivity and Depth First Search ......................239
8.1 k-connected graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 239
8.2 Depth?rst search ......................................242
8.3 2-connected graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 245
8.4 Depth?rst searchfordigraphs ...........................252
8.5 Strongly connected digraphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 253
8.6 Edge connectivity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 258
9 Colorings ..................................................261
9.1 Vertex colorings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 261
9.2 Comparability graphs and interval graphs . . . . . . . . . . . . . . . . . 265
9.3 Edge colorings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 268
9.4 Cayleygraphs..........................................271
9.5 The ?ve color theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 275
10 Circulations ...............................................279
10.1 Circulations and ?ows . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 279
10.2 Feasible circulations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 282
10.3 Elementary circulations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 289
10.4 The algorithm of Klein . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 295
10.5 The algorithm of Busacker and Gowen . . . . . . . . . . . . . . . . . . . . 299
10.6 Potentials and ε-optimality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 302
10.7 Optimal circulations by successive approximation . . . . . . . . . . . 311
10.8 A polynomial procedure REFINE . . . . . . . . . . . . . . . . . . . . . . . . 315
10.9 The minimum mean cycle cancelling algorithm . . . . . . . . . . . . . 322
10.10 Some further problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 327
10.11 An application: Graphical codes . . . . . . . . . . . . . . . . . . . . . . . . . . 329
11 The Network Simplex Algorithm ..........................343
11.1 The minimum cost ?ow problem . . . . . . . . . . . . . . . . . . . . . . . . . 344
11.2 Tree solutions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 346
11.3 Constructing an admissible tree structure . . . . . . . . . . . . . . . . . . 349
11.4 The algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 353
11.5 E?cient implementations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 358
12 Synthesis of Networks .....................................363
12.1 Symmetric networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 363
12.2 Synthesis of equivalent ?ow trees . . . . . . . . . . . . . . . . . . . . . . . . . 366
12.3 Synthesizing minimal networks . . . . . . . . . . . . . . . . . . . . . . . . . . . 373
12.4 Cut trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 379
12.5 Increasing the capacities . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 383
13 Matchings .................................................387
13.1 The 1-factor theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 387
13.2 Augmenting paths . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 390
13.3 Alternating trees and blossoms . . . . . . . . . . . . . . . . . . . . . . . . . . . 394
13.4 The algorithm of Edmonds . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 400
13.5 Matching matroids . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 416
14 Weighted matchings .......................................419
14.1 The bipartite case . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 420
14.2 The Hungarian algorithm. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 421
14.3 Matchings, linear programs, and polytopes . . . . . . . . . . . . . . . . . 430
14.4 The general case . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 434
14.5 The Chinese postman . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 438
14.6 Matchings and shortest paths . . . . . . . . . . . . . . . . . . . . . . . . . . . . 442
14.7 Some further problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 449
14.8 An application: Decoding graphical codes . . . . . . . . . . . . . . . . . . 452
15 A Hard Problem: The TSP ................................457
15.1 Basic de?nitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 457
15.2 Lower bounds: Relaxations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 460
15.3 Lower bounds: Subgradient optimization . . . . . . . . . . . . . . . . . . 466
15.4 Approximation algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 471
15.5 Upper bounds: Heuristics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 477
15.6 Upper bounds: Local search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 480
15.7 Exact neighborhoods and suboptimality . . . . . . . . . . . . . . . . . . . 483
15.8 Optimal solutions: Branch and bound . . . . . . . . . . . . . . . . . . . . . 489
15.9 Concluding remarks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 497
A Some NP-Complete Problems .............................501
B Solutions ..................................................509
B.1 Solutions for Chapter 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 509
B.2 Solutions for Chapter 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 515
B.3 Solutions for Chapter 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 520
B.4 Solutions for Chapter 4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 527
B.5 Solutions for Chapter 5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 532
B.6 Solutions for Chapter 6 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 535
B.7 Solutions for Chapter 7 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 545
B.8 Solutions for Chapter 8 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 554
B.9 Solutions for Chapter 9 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 560
B.10 Solutions for Chapter 10 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 563
B.11 Solutions for Chapter 11 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 572
B.12 Solutions for Chapter 12 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 572
B.13 Solutions for Chapter 13 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 578
B.14 Solutions for Chapter 14 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 583