research
这是 从带权图到流形测地线 的第 1 篇。
有限连通图 \(G\),边权 \(w:E\to\mathbb{R}_{>0}\)。图距离 \(d_G\) 是最短路长,Dijkstra 可以精确算出来。流形上的距离是能量
\[ d_g(x,y)=\inf_\gamma\int\sqrt{g(\dot\gamma,\dot\gamma)}\,dt \]
的下确界,实现它的曲线是测地线。最初的希望是:给顶点一个嵌入 \(\iota:V\to M\),使所有成对距离都相等,
\[ d_g(\iota(u),\iota(v))=d_G(u,v). \]
三角等式
设 \(o\) 连着三条边,另一端是 \(a,b,c\)。图距离满足
\[ d_G(a,b)=d_G(a,o)+d_G(o,b). \]
在长度空间里,这当且仅当 \(o\) 落在某条从 \(a\) 到 \(b\) 的极小测地线上。于是 \(\iota(o)\) 必须同时躺在 \(a\)–\(b\) 和 \(a\)–\(c\) 两条极小测地线上。
光滑黎曼流形,以及强凸的光滑 Finsler 流形,局部测地唯一:过一点、沿一个初始方向,只能射出一条。从 \(\iota(o)\) 指向 \(b\) 和指向 \(c\) 的方向就都必须和指向 \(a\) 的方向相反,\(b\) 和 \(c\) 落到同一条射线上,和三条不同的边矛盾。
所以只要有一个度数至少 3 的顶点,就不能把全体顶点等距嵌进光滑流形,还让所有成对距离都等于图距离。未赋权的跳数距离见 Huang–Li。赋权情形用这条三角等式更直接。
精确版本停在哪里
精确版本只能停在度量图:每条边换成区间 \([0,w_e]\),端点粘起来。那已经是测地度量空间,最短路就是测地线,只是分支点不是流形。
把这张度量图嵌成流形里的 geodesic net 也不够。环境里的测地线会抄近路,\(d_g 精确等距从目标里拿掉。留下来两件可以分开写的事:长度上 \(d_g\) 从下方逼近 \(d_G\),误差可控;走法上,从实现这段距离的曲线读出一条图上的途径。 下一篇写能做的度量:公路度量。