在最短路径发现中，在无向图中存在证明瓶颈节点的提示

Question

鉴于我有一个图G =（v，e）如果从s到t的距离严格大于| v |/2，则必须在图形。瓶颈节点定义为：删除后，S和T将不再连接。

我知道这个问题的一般算法，但我无法找到一种证明这一点的方法。我继续跑回圆形逻辑或最终给出算法以找到瓶颈节点。

现在有任何提示可以使用直接证明，证明是矛盾的，还是Pigonhol的原理？

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 |

这是矛盾。