我必须给出如下算法:
给定一个无向连通图 G，给出一个算法来找到两个节点 x,y，使得它们的距离至少为图直径的一半。证明任何主张。
我假设我必须从任意节点运行 BFS 并找到其最远的节点来查找直径。然后找到两个距离大于直径一半的探索节点。 但我怀疑这是否是最佳方案并要求解决方案。有没有其他方法可以在运行 BFS 查找直径时同时找到这两个所需的节点？使得复杂度保持多项式。 任何指导或提示将不胜感激!
最佳答案
图的直径(我们称之为 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 (与 k>=1 )。但随后，通过x ，我们最多可以在2 * (D/2 - k) = D - 2k内找到从任何节点到所有其他节点的路径。 - 因此，图表的直径不能是 D ，但是D - 2k .
关于查找距离至少为(无向)图直径一半的任意两个节点的算法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/64348406/