Combinatorics (Fall 2010)/Problem set 5

Problem 1

最短路径问题（shortest path problem）定义如下：输入为一个 directed graph $G(V,E)$；图上有两个特别的点：起点 $s\in V$ 和终点 $t\in V$。我们求由 $s$ 到 $t$ 的最短路径的长度。

1. 为这个问题写一个整数规划。（提示：一条由s到t的路径可以视为一个 s-t flow。）
2. 考虑输入图为一个weighted directed graph $G(V,E)$，每条有向边 $(i,j)\in E$ 具有一个非负的weight $w_{ij}\ge 0$。路径长度为路径上边的 weight 之和。为这个版本的最短路径问题写一个整数规划。
3. 证明：对于以上整数规划的线性规划，总存在一个最优解，所有变量的值都是整数（即我们可以通过解LP来求最短路径）。

Problem 2

1. 为 maximum matching in bipartite graph 写一个线性规划，并证明其为totally unimodular。
2. 求上述线性规划的 dual 规划，证明其为 minimum vertex cover in bipartite graph。
3. 证明 König-Egerváry Theorem。

Problem 3

输入为一个无向图 $G(V,E)$，未必连通，每条边 $uv\in E$ 有一个权重 $c_{uv}>0$。设计一个算法，找到具有最大总权重的边集 $D\subseteq E$，使得 $G(V,E\setminus D)$ 和 $G(V,E)$ 具有相同的连通子图个数。