2012级--讨论记录 (第三学期)

2013年9月6日

[课件下载]

1. Bellman-Ford算法。
2. Dijkstra算法。
3. 最短路问题的应用：
   • 差分约束问题：制作番茄炒蛋的时间表。
   • 设备更新问题。

2013年9月13日

[课件下载]

1. 简单的动态规划法。
2. Floyd-Warshall算法。
3. Johnson算法。
4. 多源最短路问题的应用。
   • 选址问题。
   • 最宽路问题：Schulze投票法。

2013年9月20日

[课件下载]

1. 最大/最小 点/边 独立/覆盖集，及其相互关系。
2. 最大匹配算法。
   • 增广路算法。
   • Hopcroft-Karp算法。
   • Edmonds算法。
3. 独立/覆盖问题的应用。
   • 教室分配问题。
   • 公园选址问题。
   • 剪纸问题。

2013年9月27日

[课件下载]

1. 连通度。
   • 点/边连通度和k点/边连通，及分情况举例。
   • 惠特尼定理，及分情况举例。
   • 3-正则图点、边连通度相等的证明。
2. 块。
   • 块及其性质。
   • 块-割点图及其性质。
   • 块算法。
3. k连通图。
   • x-y cut。
   • Menger定理。
   • 连通度和不交路之间的联系。