L008 最小生成树和赋权欧拉图

最小生成树

对于连通赋权图 \(G=\left\langle V,E,w\right\rangle\)，边权和最小的生成树称作「最小生成树」（minimum spanning tree）。

「普里姆算法」（Prim's algorithm）

【Algo.6.2】

Th.6.2

「克拉斯克尔算法」（Kruskal's algorithm）

【Algo.6.3】

Th.6.3

赋权欧拉图

「中国邮递员问题」（Chinese postman problem）：寻找「最优邮递路线」。

「邮递路线」（post walk）：经过每条边至少一次的闭路线。其权定义为路线中边的边权之和，重复经过重复计入。

「最优邮递路线」：权和最小的邮递路线。

Th.6.4 存在一条最优邮递路线，其对应重边的集合 \(E^\text{M}\) 是以赋权图 \(G\) 中所有 \(2k(k\ge 0)\) 个度为奇数的顶点为起点和 \(k\) 条无公共边的最短路经过的边的集合。

「最小权完美匹配」（minimum-weight perfect matching）：对于赋权图，权和最小的完美匹配。可以采用花算法的变体基于线性规划计算。

「埃德蒙兹-约翰逊算法」（Edmonds-Johnson algorithm）。

【Algo.6.4】

旅行商问题

「旅行商问题」（TSP, traveling salesman problem）：找出赋权图中最短的哈密尔顿圈。

「度量旅行商问题」（\(\Delta\)-TSP, metric traveling salesman problem）：赋权函数满足三角不等式的旅行商问题。

\(\Delta\)-TSP 是一个「NP 难」（NP-hard）的优化问题。

「最近邻点算法」（nearest neighbor algorithm）

【Algo.6.5】

Th.6.5

「 克里斯托菲德斯-谢尔久科夫算法」（Christofides-Serdyukov algorithm）

【Algo.6.6】

Th.6.6