删除无向图中的节点,该节点销毁其他两个节点之间的路径

Question

我需要帮助解决我目前正在处理的这个问题,这个问题涉及在无向图中找到一个节点v,当被删除时,将破坏另外两个节点s和t之间的所有路径.

假设n节点无向图G =(V,E)包含两个节点s和t,使得s和t之间的距离严格大于n/2.表明必须存在某个节点v,不等于s或t,这样从G中删除v会破坏所有st路径.(换句话说,通过删除v从G获得的图形不包含从s到t的路径.)

给出一个运行时间为O(m + n)的算法来找到这样一个节点v.
(对于解决方案,你可以使用普通英语或伪代码.)

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

Answer 1

首先是证明部分:

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

第二部分算法:

使用双向BFS.由于如果你开始从s和t搜索v节点,它们肯定会在v节点上相遇.在最坏的情况下,你通过所有的V和E,所以它是O(V + E).