在最短路徑查找過程中在無向圖中存在證明瓶頸節點的提示

Question

假設從s到t的距離嚴格大於| V |/2，我有一個圖G =（V，E）圖中的瓶頸節點。瓶頸節點是被定義爲的節點：當被移除時，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 |

這就是矛盾。