algorithm - 删除无向图中的节点会破坏其他两个节点之间的路径

Question

我需要帮助解决我目前正在处理的这个问题，它涉及在无向图中找到节点 v，当删除该节点时，将破坏其他两个节点 s 和 t 之间的所有路径。

Suppose that an n-node undirected graph G = (V, E) contains two nodes s and t such that the distance between s and t is strictly greater than n/2. Show that there must exist some node v, not equal to either s or t, such that deleting v from G destroys all s-t paths. (In other words, the graph obtained from G by deleting v contains no path from s to t.)

Give an algorithm with running time O(m + n) to find such a node v.
(For solution, you can use either plain English or pseudo code.)

我对此的理解是，解决方案将涉及创建广度优先搜索以找到节点 v 并将其删除，但我不确定如何首先证明删除节点存在，从而删除它会破坏所有 s-t 路径。

Answer 1

首先是证明部分:

假设 v 节点不存在，这意味着从 s 到 t 至少有两条路径使用完全不同的节点，并且距离大于 n/2。这是不可能的，因为您甚至没有足够数量的节点对于这两条路。所以这与我们存在 v 节点的假设相矛盾。

第二部分算法:

使用双向 BFS。如果从 s 和 t 开始搜索，v 节点的存在，它们肯定会在 v 节点相遇。在最坏的情况下，你遍历了所有的 V 和 E，所以它是 O(V + E)。