algorithm - 在最短路径查找期间证明无向图中存在瓶颈节点的提示

Question

鉴于我有一个图 G = (V, E)，如果从 s 到 t 的距离严格大于 |V|/2，则图中一定存在瓶颈节点。瓶颈节点是定义为:删除后，s 和 t 将不再连接的节点。

我知道这个问题的一般算法，但我想不出一种方法来证明这一点。我不断地回到循环逻辑或只是结束给出算法来找到瓶颈节点。

现在有任何提示可以使用直接证明、反证法或归类原理来证明这一点吗？

Answer 1

反证法:

设 s 和 t 有一条长度为 |P1| 的最小路径 P1 > |v|/2。假设 P1 中没有瓶颈节点意味着在 s 和 t 之间存在一条替代的、不相交的路径 P2(仅共享节点 s 和 t)。由于 P1 的长度最短，我们知道 |P2|>=|P1|。

现在，图中的节点总数必须至少是 P1 和 P2 的并集中的节点数:

|v| >= |P1|-1 + |P2|-1 + 2 = |P1| + |P2| >= 2|P1| > |v|

这就是矛盾所在。