Combinatorics (Fall 2010)/Problem set 5

From EtoneWiki
Jump to: navigation, search

Problem 1

最短路径问题(shortest path problem)定义如下:输入为一个 directed graph ;图上有两个特别的点:起点 和终点 。我们求由 的最短路径的长度。

  1. 为这个问题写一个整数规划。(提示:一条由s到t的路径可以视为一个 s-t flow。)
  2. 考虑输入图为一个weighted directed graph ,每条有向边 具有一个非负的weight 。路径长度为路径上边的 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

输入为一个无向图 ,未必连通,每条边 有一个权重 。设计一个算法,找到具有最大总权重的边集 ,使得 具有相同的连通子图个数。