文档介绍：A Course binatorial Optimization
Alexander Schrijver
CWI,
Kruislaan 413,
1098 SJ Amsterdam,
herlands
and
Department of Mathematics,
University of Amsterdam,
Plantage Muidergracht 24,
1018 TV Amsterdam,
herlands.
November 9, 2004
copyright c A. Schrijver
Contents
1. Shortest paths and trees 5
. Shortest paths with nonnegative lengths 5
. Speeding up Dijkstra’s algorithm with heaps 9
. Shortest paths with arbitrary lengths 12
. Minimum spanning trees 19
2. Polytopes, polyhedra, Farkas’ lemma, and linear programming 23
. Convex sets 23
. Polytopes and polyhedra 25
. Farkas’ lemma 31
. Linear programming 33
3. Matchings and covers in bipartite graphs 39
. Matchings, covers, and Gallai’s theorem 39
. K˝onig’s theorems 40
. Cardinality bipartite matching algorithm 44
. Weighted bipartite matching 47
. The matching polytope 50
4. Menger’s theorem, flows, and circulations 53
. Menger’s theorem 53
. Path packing algorithmically 57
. Flows works 60
. Finding a maximum flow 62
. Speeding up the maximum flow algorithm 67
. Circulations 70
. Minimum-cost flows 72
5. Nonbipartite matching 79
. Tutte’s 1-factor theorem and the Tutte-Berge formula 79
. Cardinality matching algorithm 82
. Weighted matching algorithm 86
. The matching polytope 93
. The Cunningham-Marsh formula 96
6. Problems, algorithms, and running time 98
. Introduction 98
. Words 99
. Problems 101
. Algorithms and running time 101
. The class NP 102
. pleteness 104
. pleteness of the satisfiability problem 104
. pleteness of some other problems 107
. Turing machines 109
7. Cliques, cocliques, and colourings 112
. Introduction 112
. Edge-colourings of bipartite graphs 116
. Partially ordered sets 122
. Perfect graphs 125
. Chordal graphs 129
8. Integer linear programming and totally unimodul