查找距离至少为（无向）图直径一半的任意两个节点的算法
Algorithm to find any two nodes with distance of at least half the (undirected) graph's diameter
我要给出一个算法如下：
给定一个无向连通图 G，给出一个算法找到两个节点 x,y，使得它们的距离至少是图直径的一半。证明任何说法。
我假设我必须 运行 来自任意节点的 BFS 并找到它的最远节点以找到直径。然后找到距离大于直径一半的两个已探索节点。
但我怀疑这是最优的，并要求解决方案。 运行在BFS求直径的时候，有没有其他办法，同时求出这两个需要的节点？所以复杂度仍然是多项式的。
任何指导或提示将不胜感激！
这实际上是一个棘手的问题，但我想我明白了。有趣的是，你部分错误的解决方案让我走上了正确的道路。
让我们在这里复制一些定义：
- 图中两个顶点之间的距离是最短路径中的边数
- 顶点
v 的偏心率是 v 与任何其他顶点之间的最大距离
- 图的直径
d是图中任意顶点的最大偏心率。也就是说，d是任意一对顶点之间的最大距离
真正的问题是实际找到直径，这不是一件容易的事。要找到直径，您不能只选择任何节点和 运行 BFS - 在这种情况下，您只能找到距离该节点（偏心率）最远的节点，但它不是直径。要实际找到直径，您必须从每个节点进行 运行 BFS（=找到偏心率），并且您得到的最大距离是直径（有一些更好的算法，但正如我所说 - 这不是简单的任务）。
但是！您根本不必知道直径。如果您实际上 运行 来自随机节点的 BFS，并且您找到距离最大（偏心率）的节点 - 这就是您算法的解决方案。 x 将是您的起始节点，y 将是距离最远的节点。
为什么？如果你想象像这样的超级简单的图
你可以看到直径在节点 1 和节点 4 之间。所以无论你从哪个点 运行 BFS，那个点都必须在中间（这意味着它将有一半直径）或不在中间然后距离最大的节点必须具有比直径的一半更高的距离。
再复杂的图表也改变不了事实
如果你选择6或7，它不完全是直径路径（因为最远距离在1-2-3-4-5之间），但它意味着你得到更高的距离，这对你的任务。
结果：运行来自随机节点的BFS，当它结束时，取与起始节点距离最大的节点（=找到偏心率并记住最远的节点）并且起始和“结束”节点是(x,y)
图的直径（我们称之为 D）是其任何节点之间的最大距离（= 最小跳数）。
选择任何节点并执行 BFS，同时为每个节点保留从初始节点开始的跳数。这需要 O(V)，因为您将只访问所有节点一次。请注意，此 number of hops 也是 shortest distance to v from the root - 我将其称为 d(root, v).
现在，从你的根中取出跳数最多的叶 z。恭喜，d(root, z) >= D/2，因为
引理：对于直径D的连通图中的任意节点x，必定存在一个节点y位于至少D/2远。
证明：如果不是这样，那么就会有一些节点 x 这样，对于所有 y，d(x,y) = D/2 - k <= D/2 （k>=1）。但是，通过 x，我们最多可以在 2 * (D/2 - k) = D - 2k 中找到从任何节点到所有其他节点的路径 - 因此，图的直径不可能是 D，而是 [=27] =].
我要给出一个算法如下：
给定一个无向连通图 G，给出一个算法找到两个节点 x,y，使得它们的距离至少是图直径的一半。证明任何说法。
我假设我必须 运行 来自任意节点的 BFS 并找到它的最远节点以找到直径。然后找到距离大于直径一半的两个已探索节点。 但我怀疑这是最优的，并要求解决方案。 运行在BFS求直径的时候，有没有其他办法，同时求出这两个需要的节点？所以复杂度仍然是多项式的。 任何指导或提示将不胜感激！
这实际上是一个棘手的问题，但我想我明白了。有趣的是，你部分错误的解决方案让我走上了正确的道路。
让我们在这里复制一些定义：
- 图中两个顶点之间的距离是最短路径中的边数
- 顶点
v的偏心率是v与任何其他顶点之间的最大距离 - 图的直径
d是图中任意顶点的最大偏心率。也就是说，d是任意一对顶点之间的最大距离
真正的问题是实际找到直径，这不是一件容易的事。要找到直径，您不能只选择任何节点和 运行 BFS - 在这种情况下，您只能找到距离该节点（偏心率）最远的节点，但它不是直径。要实际找到直径，您必须从每个节点进行 运行 BFS（=找到偏心率），并且您得到的最大距离是直径（有一些更好的算法，但正如我所说 - 这不是简单的任务）。
但是！您根本不必知道直径。如果您实际上 运行 来自随机节点的 BFS，并且您找到距离最大（偏心率）的节点 - 这就是您算法的解决方案。 x 将是您的起始节点，y 将是距离最远的节点。
为什么？如果你想象像这样的超级简单的图
你可以看到直径在节点 1 和节点 4 之间。所以无论你从哪个点 运行 BFS，那个点都必须在中间（这意味着它将有一半直径）或不在中间然后距离最大的节点必须具有比直径的一半更高的距离。
再复杂的图表也改变不了事实
如果你选择6或7，它不完全是直径路径（因为最远距离在1-2-3-4-5之间），但它意味着你得到更高的距离，这对你的任务。
结果：运行来自随机节点的BFS，当它结束时，取与起始节点距离最大的节点（=找到偏心率并记住最远的节点）并且起始和“结束”节点是(x,y)
图的直径（我们称之为 D）是其任何节点之间的最大距离（= 最小跳数）。
选择任何节点并执行 BFS，同时为每个节点保留从初始节点开始的跳数。这需要 O(V)，因为您将只访问所有节点一次。请注意，此 number of hops 也是 shortest distance to v from the root - 我将其称为 d(root, v).
现在，从你的根中取出跳数最多的叶 z。恭喜，d(root, z) >= D/2，因为
引理：对于直径D的连通图中的任意节点x，必定存在一个节点y位于至少D/2远。
证明：如果不是这样，那么就会有一些节点 x 这样，对于所有 y，d(x,y) = D/2 - k <= D/2 （k>=1）。但是，通过 x，我们最多可以在 2 * (D/2 - k) = D - 2k 中找到从任何节点到所有其他节点的路径 - 因此，图的直径不可能是 D，而是 [=27] =].