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 first 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 Constructingblockingflows..............................176

6.5 Zero-oneflows .........................................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 Depthfirst search ......................................242

8.3 2-connected graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 245

8.4 Depthfirst 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 five color theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 275

10 Circulations ...............................................279

10.1 Circulations and flows . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 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 flow problem . . . . . . . . . . . . . . . . . . . . . . . . . 344

11.2 Tree solutions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 346

11.3 Constructing an admissible tree structure . . . . . . . . . . . . . . . . . . 349

11.4 The algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 353

11.5 Efficient implementations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 358

12 Synthesis of Networks .....................................363

12.1 Symmetric networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 363

12.2 Synthesis of equivalent flow 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 definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 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