algorithm - 如何正确绘制满足三角不等式的完整5顶点无向图

Question

除了暴力破解之外，我如何有效地绘制具有不同边权重 {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} 的正确完整 5 顶点无向图以满足三角不等式？我不知道有任何算法可以为提供的边权重生成正确的图 G。

Here's an example of a Complete 5-Vertex Graph

Answer 1

这是一个有效的方法。

(2,1):  1
(3,1):  2
(3,2):  3
(4,1):  4
(4,2):  5
(4,3):  6
(5,1):  7
(5,2):  8
(5,3):  9
(5,4): 10

n 顶点完全图的泛化应该很清楚。正确性的证明是归纳的。对于 n = 0，这是显而易见的。对于更高的 n，归纳假设等价于三角不等式的每次违反都涉及顶点 n 的命题。涉及顶点 n 的边比其他边长，因此 n 不是违规的过渡顶点。因此，每个假设的违反(直到对称)看起来都是 n -> v -> w。存在一些常量 c，使得 n -> v 的长度为 c + v，而 n -> w 的长度为 c + w。因此，如果 v -> w 是违规的，那么它的长度小于 w - v，通过检查，这是不可能的。