文档介绍：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.
February 7, 2003
copyright c A. Schrijver
Contents
1. Shortest paths and trees 4
. Shortest paths with nonnegative lengths 4
. Speeding up Dijkstra’s algorithm with heaps 6
. Shortest paths with arbitrary lengths 9
. Minimum spanning trees 14
2. Polytopes, polyhedra, Farkas’ lemma, and linear programming 18
. Convex sets 18
. Polytopes and polyhedra 19
. Farkas’ lemma 23
. Linear programming 25
3. Matchings and covers in bipartite graphs 30
. Matchings, covers, and Gallai’s theorem 30
. K˝onig’s theorems 31
. Cardinality bipartite matching algorithm 33
. Weighted bipartite matching 35
. The matching polytope 38
4. Menger’s theorem, flows, and circulations 41
. Menger’s theorem 41
. Path packing algorithmically 43
. Flows works 46
. Finding a maximum flow 47
. Speeding up the maximum flow algorithm 51
. Circulations 54
. Minimum-cost flows 55
5. Nonbipartite matching 61
. Tutte’s 1-factor theorem and the Tutte-Berge formula 61
. Cardinality matching algorithm 63
. Weighted matching algorithm 66
. The matching polytope 70
. The Cunningham-Marsh formula 72
6. Problems, algorithms, and running time 74
. Introduction 74
. Words 75
. Problems 76
. Algorithms and running time 76
. The class NP 77
. pleteness 78
. pleteness of the satisfiability problem 78
. pleteness of some other problems 80
. Turing machines 82
7. Cliques, cocliques, and colourings 84
. Introduction 84
. Edge-colourings of bipartite graphs 87
. Partially ordered sets 91
. Perfect graphs 94
. Chordal graphs 97
8. Integer linear programming and totally unimodular matrices 100