algorithm - 无向图中直径和半径的关系？

Question

我们只考虑无向图。图的直径是顶点s和t的所有选择中之间最短路径距离的最大值 和 t 。 (回想一下 s 和 t 之间的最短路径距离是 s-t 路径中边的最少数量。)接下来，对于一个顶点 s，让 l(s) 表示 s 之间的最短路径距离在所有顶点 t 上的最大值> 和 t。图的半径 是l(s) 中顶点s 的所有选择的最小值。对于半径 r 和直径 d 以下哪项始终成立？选择最佳答案。

1) r >= d/2
2) r <= d

我们知道 (1) 和 (2) 总是适用于任何写成的引用书。我的挑战是入学考试中提到的这个问题，只有 (1) 或 (2) 中的一个应该是正确的，OP 说选择最佳答案，在考试答题纸上写下 (1) 是最佳选择。如何验证我，为什么 (1) 优于 (2)。

Answer 1

他们都是真的。不要让模棱两可的考试削弱您的概念。

至于证明:

首先，第二个不等式非常微不足道(从定义本身来看)

现在是第一个

d <= 2*r

设z为中心顶点，则:

e(z)=r

现在，

diameter = d(x,y)       [d(x,y) denotes distance between some vertex x & y]

d(x,y) <= d(x,z) + d(z,y)

d(x,y) <= d(z,x) + d(z,y)

d(x,y) <= e(z) + e(z)       [this can be an upper bound as e(z)>=d(z,u) for all u]

diameter <= 2*r