路径距离测量的最小数量

Question

考虑一个具有边集E和顶点V的赋权图。

目标是找到所有边的权重。您可以访问路径的距离。

例如，路径ABCD的距离是AB、BC、CD的边权重之和。

选择最小路径数的策略是什么，以便通过知道这些距离，可以计算所有的边权重。

Answer 1

对于一个有N条边的图，你至少需要N个测量值。因此，获得所有权重的最简单方法是分别测量每条边。

证明：每个测量值都可以看作是一个线性方程，其中边权重是变量。总而言之，这些测量结果构成了一个线性方程组。如果你的方程(测量值)少于变量(长度)，你就会得到一个有无限多个解的undetermined system。