无向图中直径与半径的关系？

Question

我们只考虑无向图。图的直径是s与t之间最短路径距离的最大，在顶点s和t的所有选择上。(回想一下s和t之间的最短路径距离是s-t路径中的最少边缘数。)接下来，对于顶点s，设l(s)表示s和t之间最短路径距离在所有顶点t上的最大值。图的半径是顶点s的所有选择的l(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

Answer 2

他们俩都挺住。

2)应明确。

1)采用三角形不等式。我们可以使用这个属性，因为图上的距离是度量(%28mathematics%29)。设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) <=半径(G)。然后我们得到直径(G)= d(x，z) <= d(y，v) + d(v，z) <= 2*半径(G)。

Answer 3

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 always >= min。

(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) >= dist(A, B)，即2 * r >= d。

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