没有合适的资源?快使用搜索试试~ 我知道了~
A course in combinatorial optimization (A. Schrijver)
4星 · 超过85%的资源 需积分: 9 15 下载量 41 浏览量
2014-11-28
11:03:15
上传
评论
收藏 1.3MB PDF 举报
温馨提示
试读
163页
A course in combinatorial optimization (A. Schrijver) 经典的组合优化教材
资源推荐
资源详情
资源评论
A Course in Combinatorial Optimization
Alexander Schrijver
CWI,
Kruislaan 413,
1098 SJ Amsterdam,
The Netherlands
and
Department of Mathematics,
University of Amsterdam,
Plantage Muidergracht 24,
1018 TV Amsterdam,
The Netherlands.
February 7, 2003
copyright
c
A. Schrijver
Contents
1. Shortest paths and trees 4
1.1. Shortest paths with nonnegative lengths 4
1.2. Speeding up Dijkstra’s algorithm with heaps 6
1.3. Shortest paths with arbitrary lengths 9
1.4. Minimum spanning trees 14
2. Polytopes, polyhedra, Farkas’ le mma, and linear programming 18
2.1. Convex sets 18
2.2. Polytopes and polyhedra 19
2.3. Farkas’ lemma 23
2.4. Linear programming 25
3. Matchings and covers in bipartite graphs 30
3.1. Matchings, covers, and Gallai’s theorem 30
3.2. K˝onig’s theorems 31
3.3. Cardinality bipartite matching algorithm 33
3.4. Weighted bipartite matching 35
3.5. The matching polytope 38
4. Menger’s theorem, flows, and circulations 41
4.1. Menger’s theorem 41
4.2. Path packing algorithmically 43
4.3. Flows in networks 46
4.4. Finding a maximum flow 47
4.5. Speeding up the maximum flow algorithm 51
4.6. Circulations 54
4.7. Minimum-cost flows 55
5. Nonbipartite matching 61
5.1. Tutte’s 1-factor theorem and the Tutte-Berge formula 61
5.2. Cardinality matching algorithm 63
5.3. Weighted matching algorithm 66
5.4. The matching polytope 70
5.5. The Cunningham-Marsh formula 72
6. Problems, algorithms, and running time 74
6.1. Introduction 74
6.2. Words 75
6.3. Problems 76
6.4. Algorithms and running time 76
6.5. The class NP 77
6.7. NP-completeness 78
6.8. NP-completeness of the satisfiability problem 78
6.9. NP-completeness of some other problems 80
6.10. Turing machines 82
7. Cliques, cocliques, and colourings 84
7.1. Introduction 84
7.2. Edge-colourings o f biparti te graphs 87
7.3. Partially ordered sets 91
7.4. Perfect graphs 94
7.5. Chordal graphs 97
8. Integer linear programming and totally unimodular matrices 100
8.1. Integer linear programming 100
8.2. Totally unimodular matrices 101
8.3. Totally unimodular matrices fro m biparti t e graphs 104
8.4. Totally unimodular matrices fro m directed graphs 108
9. Multicommo dity flows and disjoint paths 111
9.1. Introduction 111
9.2. Two commodities 114
9.3. Disjoint paths in acyclic directed graphs 117
9.4. Vertex-disjoint paths in planar graphs 119
9.5. Edge-disjoint paths in planar gra phs 124
9.6. A column generation technique for multicommodity flows 126
10. Matroids 129
10.1. Matroids and the greedy algorithm 129
10.2. Equivalent axioms for matroids 13 1
10.3. Examples of matroids 134
10.4. Two technical lemmas 136
10.5. Matroid intersection 137
10.6. Weighted matroid intersection 141
10.7. Matroids and polyhedra 144
References 148
Name index 155
Subject index 157
4 Chapter 1. Shortest paths and trees
1. Shortest paths and tre e s
1.1. Shortest paths with nonnegative lengths
Let D = (V, A) be a directed graph, and let s, t ∈ V . A path is a sequence P = (v
0
, a
1
, v
1
, . . . , a
m
, v
m
)
where a
i
is an arc from v
i−1
to v
i
for i = 1, . . . , m. If s = v
0
and t = v
m
, the vertices s and t are
the starting and end vertex of P , respectively, and P is called an s − t path. The length of P is m.
The d is tance from s to t is the minimum length of any s − t path. (If no s − t pat h exists, we set
the distance from s to t equal to ∞.)
It is not difficult to determine the distance from s to t: Let V
i
denote the set of vertices of D at
distance i from s. Note that for each i:
V
i+1
is equal to the set of vertices v ∈ V \ (V
0
∪ V
1
∪ ··· ∪ V
i
) for which (u, v) ∈ A
for some u ∈ V
i
.
(1)
This gives us directly an algorithm for det ermining the sets V
i
: we set V
0
:= {s} and next we
determine with rule (1) the sets V
1
, V
2
, . . . successively, until V
i+1
= ∅.
In fact, it gives a linear-time algorithm:
Theorem 1.1. The algorithm has running time O(|A|).
Proof. Direct ly from the description.
In fact the algorithm finds the distance from s to all vertices reachable from s. Moreover, it
gives the shortest paths. These can be described by a rooted (directed) tree T = (V
0
, A
0
), with root
s, such that V
0
is the set of vertices reachable in D from s and such that for each u, v ∈ V
0
, each
directed u − v path in T is a shortest u − v path in D.
1
Indeed, when we reach a vertex t in the algorithm, we store the arc by which t is reached. Then
at the end of the algorithm, all stored arcs form a rooted t re e with this property.
There is also a trivial min-max relation characterizing the minimum length of an s −t path. To
this end, call a subset A
0
of A an s − t cut if A
0
= δ
out
(U) for some subset U of V satisfying s ∈ U
and t 6∈ U.
2
Then the following was observed by Robacker [1956]:
Theorem 1.2. The minimum length of an s − t path is equal to the maximum number of pairwise
disjoint s − t cuts.
Proof. Trivially, the minimum is at least the maximum, since each s − t path intersects each s − t
cut in an arc. The fact that the minimum is equal to the maximum follows by considering the s −t
cuts δ
out
(U
i
) for i = 0, . . . , d − 1, where d is the distance f rom s to t and where U
i
is the set of
vertices of distance at most i from s.
This can be generalized to the case where arcs have a certain ‘length’. For any ‘length’ function
l : A → Q
+
and any path P = ( v
0
, a
1
, v
1
, . . . , a
m
, v
m
), let l(P ) be the length of P . That is:
l(P ) :=
m
X
i=1
l(a).(2)
Now the distance from s to t (with respect to l) is equal to the minimum length of any s − t path.
If no s − t path exists, the distance is +∞.
1
A rooted tree, with root s, is a directed graph s uch that the underlying undirected graph is a tree and such that
each vertex t 6= s has indegree 1. Thus each vertex t is reachable from s by a unique directed s − t path.
2
δ
out
(U) and δ
in
(U) denote the sets of arcs leaving and entering U , respectively.
Section 1.1. Shortest paths with nonnegative lengths 5
Again there is an easy algorithm, due to Dijkstra [1959], to find a minimum-length s − t path
for all t. Start wit h U := V and set f(s) := 0 and f(v) = ∞ if v 6= s. Next apply the following
iteratively:
Find u ∈ U minimizing f(u) over u ∈ U. For each a = (u, v) ∈ A for which
f(v) > f (u) + l(a), re set f (v) := f(u) + l(a). Reset U := U \ {u}.
(3)
We stop if U = ∅. Then:
Theorem 1.3. The final function f gives the distances from s.
Proof. Let dist(v ) denote the distance from s to v, for any vertex v. Trivially, f(v) ≥ dist(v) for
all v, throughout the iterations. We prove that throughout the iterations, f(v) = dist(v) for each
v ∈ V \ U. At the start of the algorithm this is trivial (as U = V ).
Consider any iteration ( 3). It suffices to show that f(u) = dist(u) for the chosen u ∈ U. Suppose
f(u) > dist(u) . Let s = v
0
, v
1
, . . . , v
k
= u be a shortest s −u path. Le t i be the smallest index with
v
i
∈ U .
Then f(v
i
) = dist(v
i
). Indeed, if i = 0, then f(v
i
) = f(s) = 0 = dist(s) = dist(v
i
). If i > 0, then
(as v
i−1
∈ V \ U):
f(v
i
) ≤ f(v
i−1
) + l(v
i−1
, v
i
) = dist(v
i−1
) + l(v
i−1
, v
i
) = dist(v
i
).(4)
This implies f (v
i
) ≤ dist(v
i
) ≤ dist(u) < f(u), contradicting the choice of u.
Clearly, the number of it erations is |V |, while each iteration takes O(|V |) time. So the algorithm
has a running time O(|V |
2
). In fact, by storing for each vertex v the last arc a for which (3) applied
we find a rooted tree T = (V
0
, A
0
) with root s such that V
0
is the set of vertices reachable from s
and such that for each u, v ∈ V
0
, each directed u − v path in T is a shortest u − v path in D.
Thus we have:
Theorem 1.4. Given a directed graph D = (V, A), s, t ∈ V , and a length function l : A → Q
+
, a
shortest s − t path can be fo und in time O(|V |
2
).
Proof. See above.
For an improvement, see Section 1.2.
A weighted version of Theorem 1.2 is as follows:
Theorem 1.5. Let D = (V, A ) be a di rected graph, s , t ∈ V , and let l : A → Z
+
. Then the minimum
length of an s−t path is equal to the maximum number k of s−t cuts C
1
, . . . , C
k
(repetition allowed)
such that each arc a is in at most l(a) of the cuts C
i
.
Proof. Again, the minimum is not smaller than the maximum, since if P is any s − t path and
C
1
, . . . , C
k
is any collection as described in the theorem:
3
l(P ) =
X
a∈AP
l(a) ≥
X
a∈AP
( number of i with a ∈ C
i
)
=
k
X
i=1
|C
i
∩ AP | ≥
k
X
i=1
1 = k.
(5)
To see equality, let d be the distance from s to t, and let U
i
be the set of vertices at distance less
than i from s, for i = 1, . . . , d. Tak ing C
i
:= δ
out
(U
i
), we obtain a collection C
1
, . . . , C
d
as required.
3
AP denotes the set of arcs traversed by P
剩余162页未读,继续阅读
资源评论
- qq_198842712014-11-28有点难懂,但是表示感谢
robbuaa
- 粉丝: 0
- 资源: 2
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功