research
这是 从带权图到流形测地线 的第 4 篇。Y 形只处理一个分支。
不要嵌进平面
平面嵌入会有交叉。交叉处管子粘在一起,会造出图上没有的捷径。底空间用 ribbon:每个顶点一个圆盘,每条边一个矩形,按半边的循环序粘起来。得到带边曲面,图是它的形变收缩核。非平面图同样适用。
边 \(e\) 的矩形是 \([0,w_e]\times[-\delta,\delta]\)。共形因子在中线 \(y=0\) 上等于 1,向两侧按 \(\varphi(|y|/\delta)\) 涨到 \(1+\lambda\)。中线长度正好是 \(w_e\)。边上不能省路,测地线只在顶点圆盘里抹角。
顶点上不要各向同性
圆盘上若仍用各向同性的 \(\rho\),Y 形里那种短切还在。换成各向异性,或者 Finsler:第 \(i\) 条入射边有方向 \(\tau_i\),系数 \(\alpha_i\) 只在第 \(i\) 条走廊里小,垂直方向的系数 \(\beta\) 很大。换走廊必须付转弯费。
简单图的边色数不超过 \(\Delta+1\)。颜色可以当作分量下标,和「顶点处一条 \(n\) 维的边权」是同一件事。
三个命题
Y 形的渐近是定理 C,上一篇的表就是它的 \(p=3\)。一般图上还有两件要分开写。
距离逼近:对任意有限带权图,
\[ 0\le d_G(u,v)-d_g(u,v)\le C\,k(u,v)\,\delta\,\lambda^{-\alpha}. \]
\(k(u,v)\) 是某条最短路上的分支点数,\(\alpha\) 由 \(\varphi\) 在 0 处的阶决定,\(C\) 只依赖最大度和顶点处的最小夹角。ribbon 上夹角是组合量。
组合恢复:若 \(u,v\) 之间的最短路唯一,并且和第二短的差距大于误差项,则测地线落在这条最短路的管子里,经过的边集相同。
C 已经可以写成证明:上界用三折线族直接算,下界用共形长度的分片估计,离开便宜邻域的任何弧,长度增量至少抵消省下来的欧氏长度。前两条是这个想法能站住的核心,证明还没有写到和 C 一样干净。
下一篇说明这套构造不能拿来替换 Dijkstra:算法。