Combinatorics (Fall 2010)/Problem set 5: Difference between revisions
Jump to navigation
Jump to search
imported>WikiSysop Created page with '== Problem 1 == 最短路径问题（shortest path problem）定义如下：输入为一个 directed graph <math>G(V,E)</math>；图上有两个特别的点：起点 <math>s\in V…' |
imported>WikiSysop m Protected "Combinatorics (Fall 2010)/Problem set 5" ([edit=sysop] (indefinite) [move=sysop] (indefinite)) |
||
| (2 intermediate revisions by the same user not shown) | |||
| Line 4: | Line 4: | ||
# 为这个问题写一个整数规划。（提示：一条由s到t的路径可以视为一个 s-t flow。） | # 为这个问题写一个整数规划。（提示：一条由s到t的路径可以视为一个 s-t flow。） | ||
# 考虑输入图为一个weighted directed graph <math>G(V,E)</math>，每条有向边 <math>(i,j)\in E</math> 具有一个非负的weight <math>w_{ij}\ge 0</math>。路径长度为路径上边的 weight 之和。为这个版本的最短路径问题写一个整数规划。 | # 考虑输入图为一个weighted directed graph <math>G(V,E)</math>，每条有向边 <math>(i,j)\in E</math> 具有一个非负的weight <math>w_{ij}\ge 0</math>。路径长度为路径上边的 weight 之和。为这个版本的最短路径问题写一个整数规划。 | ||
# | # 证明：对于以上整数规划的线性规划，总存在一个最优解，所有变量的值都是整数（即我们可以通过解LP来求最短路径）。 | ||
== Problem 2 == | == Problem 2 == | ||
| Line 12: | Line 12: | ||
== Problem 3 == | == Problem 3 == | ||
输入为一个无向图 <math>G(V,E)</math>，未必连通，每条边 <math>uv\in E</math> 有一个权重 <math>c_{uv}>0</math>。设计一个算法，找到具有最大总权重的边集 <math>D\subseteq E</math>，使得 <math>G(V,E\setminus D)</math> 和 <math>G(V,E)</math> 具有相同的连通子图个数。 | |||
Latest revision as of 09:09, 12 January 2011
Problem 1
最短路径问题（shortest path problem）定义如下：输入为一个 directed graph [math]\displaystyle{ G(V,E) }[/math]；图上有两个特别的点：起点 [math]\displaystyle{ s\in V }[/math] 和终点 [math]\displaystyle{ t\in V }[/math]。我们求由 [math]\displaystyle{ s }[/math] 到 [math]\displaystyle{ t }[/math] 的最短路径的长度。
- 为这个问题写一个整数规划。（提示：一条由s到t的路径可以视为一个 s-t flow。）
- 考虑输入图为一个weighted directed graph [math]\displaystyle{ G(V,E) }[/math]，每条有向边 [math]\displaystyle{ (i,j)\in E }[/math] 具有一个非负的weight [math]\displaystyle{ w_{ij}\ge 0 }[/math]。路径长度为路径上边的 weight 之和。为这个版本的最短路径问题写一个整数规划。
- 证明：对于以上整数规划的线性规划，总存在一个最优解，所有变量的值都是整数（即我们可以通过解LP来求最短路径）。
Problem 2
- 为 maximum matching in bipartite graph 写一个线性规划，并证明其为totally unimodular。
- 求上述线性规划的 dual 规划，证明其为 minimum vertex cover in bipartite graph。
- 证明 König-Egerváry Theorem。
Problem 3
输入为一个无向图 [math]\displaystyle{ G(V,E) }[/math]，未必连通，每条边 [math]\displaystyle{ uv\in E }[/math] 有一个权重 [math]\displaystyle{ c_{uv}\gt 0 }[/math]。设计一个算法，找到具有最大总权重的边集 [math]\displaystyle{ D\subseteq E }[/math]，使得 [math]\displaystyle{ G(V,E\setminus D) }[/math] 和 [math]\displaystyle{ G(V,E) }[/math] 具有相同的连通子图个数。