找到距离至少为（无向）图直径一半的任何两个节点的算法

Question

我必须给出一个算法如下：

给定一个无向连通图 G，给出一个算法，找到两个节点 x,y，使得它们的距离至少是图直径的一半。证明任何主张。

我假设我必须从任意节点运行 BFS 并找到最远的节点来找到直径。然后找到两个探索的节点，其距离大于直径的一半。但我怀疑这是最佳的并要求解决方案。有没有其他方法可以在运行 BFS 时找到直径，同时找到这两个所需的节点？这样复杂度仍然是多项式。任何指导或提示将不胜感激！

Answer 1

图的直径（我们称之为D）是其任何节点之间的最大距离（= 最小跳数）。

选择任何节点并执行 BFS，同时为每个节点保留初始节点的跳数。这需要 O(V)，因为您将只访问所有节点一次。请注意，这number of hops也是shortest distance to v from the root- 我将其称为d(root, v).

现在，z从根中取出跃点数最多的叶子。恭喜d(root, z) >= D/2，因为

引理：对于x直径为 的连通图中的任何节点D，必须存在一个y至少D/2远离的节点。

证明：如果不是这样，那么就会有一些节点，x所以对于所有y, d(x,y) = D/2 - k <= D/2(with k>=1)。但是，通过通过x，我们最多可以找到从任何节点到所有其他节点的路径2 * (D/2 - k) = D - 2k- 因此，图的直径不能是D，而是D - 2k。