没有合适的资源?快使用搜索试试~ 我知道了~
首页A Course in Combinatorial Optimization
A Course in Combinatorial Optimization
需积分: 10 12 下载量 173 浏览量
更新于2023-03-16
评论
收藏 1.44MB PDF 举报
A Course in Combinatorial Optimization
资源详情
资源评论
资源推荐
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 3, 2013
copyright
c
° A. Schrijver
Contents
1. Shortest paths and trees 5
1.1. Shortest paths with nonnegative lengths 5
1.2. Speeding up Dijkstra’s algorithm with heaps 9
1.3. Shortest paths with arbitrary lengths 12
1.4. Minimum spanning trees 19
2. Polytopes, polyhedra, Farkas’ lemma, and linear programming 23
2.1. Convex sets 23
2.2. Polytopes and polyhedra 25
2.3. Farkas’ lemma 31
2.4. Linear programming 33
3. Matchings and covers in bipartite graphs 39
3.1. Matchings, covers, and Gallai’s theorem 39
3.2. M-augmenting paths 40
3.3. K˝onig’s theorems 41
3.4. Cardinality bipartite matching algorithm 45
3.5. Weighted bipartite matching 47
3.6. The matching polytope 50
4. Menger’s theorem, flows, and circulations 54
4.1. Menger’s theorem 54
4.2. Flows in networks 58
4.3. Finding a maximum flow 60
4.4. Speeding up the maximum flow algorithm 65
4.5. Circulations 68
4.6. Minimum-cost flows 70
5. Nonbipartite matching 78
5.1. Tutte’s 1-factor theorem and the Tutte-Berge formula 78
5.2. Cardinality matching algorithm 81
5.3. Weighted matching algorithm 85
5.4. The matching polytope 91
5.5. The Cunningham-Marsh formula 95
6. Problems, algorithms, and running time 97
6.1. Introduction 97
6.2. Words 98
6.3. Problems 100
6.4. Algorithms and running time 100
6.5. The class NP 101
6.6. The class co-NP 102
6.7. NP-completeness 103
6.8. NP-completeness of the satisfiability problem 103
6.9. NP-completeness of some other problems 106
6.10. Turing machines 108
7. Cliques, stable sets, and colourings 111
7.1. Introduction 111
7.2. Edge-colourings of bipartite graphs 116
7.3. Partially ordered sets 121
7.4. Perfect graphs 125
7.5. Chordal graphs 129
8. Integer linear programming and totally unimodular matrices 132
8.1. Integer linear programming 132
8.2. Totally unimodular matrices 134
8.3. Totally unimodular matrices from bipartite graphs 139
8.4. Totally unimodular matrices from directed graphs 143
9. Multicommodity flows and disjoint paths 148
9.1. Introduction 148
9.2. Two commodities 153
9.3. Disjoint paths in acyclic directed graphs 157
9.4. Vertex-disjoint paths in planar graphs 159
9.5. Edge-disjoint paths in planar graphs 165
9.6. A column generation technique for multicommodity flows 168
10. Matroids 173
10.1. Matroids and the greedy algorithm 173
10.2. Equivalent axioms for matroids 176
10.3. Examples of matroids 180
10.4. Two technical lemmas 183
10.5. Matroid intersection 184
10.6. Weighted matroid intersection 190
10.7. Matroids and polyhedra 194
References 199
Name index 210
Subject index 212
5
1. Shortest paths and trees
1.1. Shortest paths with nonnegative lengths
Let D = (V, A) be a directed graph, and let s, t ∈ V . A walk 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 v
0
, . . . , v
m
all are different, P is called a path.
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 walk, and, if P is a path, an s − t path. The
length of P is m. The distance from s to t is the minimum length of any s − t path.
(If no s − t path 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:
(1) 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
.
This gives us directly an algorithm for determining 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. Directly 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
′
, A
′
), with root s, such that V
′
is the set of vertices reachable in D from
s and such that for each u, v ∈ V
′
, 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 tree 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
′
of A an s − t cut if A
′
= δ
out
(U) for some
subset U of V satisfying s ∈ U and t 6∈ U.
2
Then the following was observed by
Robacker [1956]:
1
A rooted tree, with root s, is a directed graph such 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.
剩余220页未读,继续阅读
BJAIJYJ
- 粉丝: 4
- 资源: 8
上传资源 快速赚钱
- 我的内容管理 收起
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
会员权益专享
最新资源
- 2022年中国足球球迷营销价值报告.pdf
- 房地产培训 -营销总每天在干嘛.pptx
- 黄色简约实用介绍_汇报PPT模板.pptx
- 嵌入式系统原理及应用:第三章 ARM编程简介_3.pdf
- 多媒体应用系统.pptx
- 黄灰配色简约设计精美大气商务汇报PPT模板.pptx
- 用matlab绘制差分方程Z变换-反变换-zplane-residuez-tf2zp-zp2tf-tf2sos-sos2tf-幅相频谱等等.docx
- 网络营销策略-网络营销团队的建立.docx
- 电子商务示范企业申请报告.doc
- 淡雅灰低面风背景完整框架创业商业计划书PPT模板.pptx
- 计算模型与算法技术:10-Iterative Improvement.ppt
- 计算模型与算法技术:9-Greedy Technique.ppt
- 计算模型与算法技术:6-Transform-and-Conquer.ppt
- 云服务安全风险分析研究.pdf
- 软件工程笔记(完整版).doc
- 电子商务网项目实例规划书.doc
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功
评论0