algorithm - 无向图算法

Question

假设我们有一个 n 节点、m 边的无向图 G = (V; E)，并且我们有两个不同的节点，称为 s 和 t。假设 s 和 t 之间的距离严格大于 n/2 。证明有一个节点 v 与 s 和 t 不同，使得从 s 到 t 的每条路径都经过 v。给出一个运行时间为 O(n + m) 的算法来找到这样一个顶点。您不必证明您的算法是正确的，但您必须证明存在像 v 这样的顶点。

我无法弄清楚这个过去的论文问题的确切答案，请帮帮我！

Answer 1

假设 s 和 t 之间有两条不共享节点的路径。由于 s 和 t 之间的距离 > n/2，因此每条路径在 s 和 t 之间具有 >= n/2 个节点。这意味着图有 >= n+2 个节点，这是一个矛盾。

对于算法来说，找到任何路径就足够了，而不是查看连接到一侧的子图在哪里完成而不使用路径节点。详细信息：

• 如果 s 只连接到一个节点而不是我们正在寻找的那个节点。
• 如果没有，则从 s 制作 BFS
• 找到路径 st
• 查找连接到 s 的节点，而不使用来自路径 st 节点的边
• 连接部分中路径 st 上的最后一个节点是我们正在寻找的节点。