从特殊的图论模型谈开去

斯坦纳树

背景

Steiner tree problem, or minimum Steiner tree problem, named after Jakob Steiner, is an umbrella term for a class of problems in combinatorial optimization. While Steiner tree problems may be formulated in a number of settings, they all require an optimal interconnect for a given set of objects and a predefined objective function. One well-known variant, which is often used synonymously with the term Steiner tree problem, is the Steiner tree problem in graphs. Given an undirected graph with non-negative edge weights and a subset of vertices, usually referred to as terminals, the Steiner tree problem in graphs requires a tree of minimum weight that contains all terminals (but may include additional vertices). Further well-known variants are the Euclidean Steiner tree problem and the rectilinear minimum Steiner tree problem.

(这个翻译我真的尽力了.)(我再翻译一些)

Pollak−Gilbert 猜想

Pollak-Gilbert 猜想指出，平面上任意 $n$ 点集，斯坦纳最小树长与最小生成树之长的比值的最小值是 $\frac{\sqrt{3}}{2}$

求解问题

• 先通过对 $j$ 进行划分求得对于 $i,j$ 下的最优解。
• 再通过 $i,j$ 去优化 $j$ 下的其他根的答案。

图的遍历问题

(注：下文顶点和结点混用，但其实是一回事，vertex or vertice)

Edmonds-Johnson 算法

case 1: $G$ 正好有两个奇次(度)顶点

case 2: $G$$2n$ 个奇次顶点

case 3:其余情况无解