无向图中直径和半径之间的关系？

Question

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

1） r

我们知道（1）和（2）总是保存在任何写的参考书中。我的挑战是入学考试中提到的这个问题，只有（1）或（2）中的一个应该是正确的，OP说选择最佳答案，考试答题卡后写（1）是最佳选择。如何验证我，为什么（1）比（2）好。

Answer 1

OP将s和t之间的最短路径距离定义为“s-t路径中最少的边数”。这让事情变得更简单。

我们可以用一些伪代码来编写定义：

def dist(s, t):
    return min([len(path)-1 for path starts with s and ends with t])

r = min([max([dist(s, t) for t in V]) for s in V])
d = max([max([dist(s, t) for t in V]) for s in V])

其中V是所有顶点的集合。

现在（2）显然是正确的。定义本身告诉我们：max总是

（1）稍微不那么明显。它至少需要几个步骤来证明。

假设d=dist（A， B），并且r=dist（C， D），我们有

dist(C, A) + dist(C, B) >= dist(A, B),

否则路径A-C-B的长度将小于dist（A， B）。

从r的定义中，我们知道

dist(C, D) >= dist(C, A)
dist(C, D) >= dist(C, B)

因此2*dist（C， D）

那么哪一个更好呢？这取决于你如何定义“更好”。如果我们认为非常正确（或不太明显）的东西比非常正确的东西好，那么我们可能会同意（1）比（2）好。

Answer 2

他们都坚持。

2） 应该很清楚。

1）使用三角形不等式保持不变。我们可以使用这个属性，因为图上的距离是一个度量（http://en.wikipedia.org/wiki/Metric_（数学））。使用让d（x， z）=直径（G），让y是G的中心（即G中存在一个顶点v，使得d（y， v）=半径（G））。因为d（y， v）=半径（G）和d（y， v）=d（v， y），我们知道d（v， z）

Answer 3

它们都是真的。不要让问题模棱两可的考试削弱你的概念。

还有证据：

首先，第二不平等是非常微不足道的（从定义本身来看）

现在是第一个

D

设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