無向圖算法

假設我們有一個n節點m邊無向圖G =（V; E），並且我們有兩個不同的節點稱爲s和t。假設s與t之間的距離嚴格大於n/2 。證明是一個不等於s和t的節點v，這樣從s到t的每條路徑都通過v給出一個運行時間爲O（n + m）的算法來找到這樣的一個頂點。你不必證明你的算法是正確的，但你必須給出一個證明，像v這樣的頂點存在。無向圖算法

我無法弄清這個過去的紙質問題的確切答案，幫幫我！

來源

2013-10-04 user2845205

社區標準是你展示你到目前爲止做了什麼，而不僅僅是要求回答 – Spaceghost

假設s和t之間有兩條路徑，它們不共享一個節點。由於s與t之間的距離> n/2，因此每條路徑在s與t之間有> = n/2個節點。這意味着圖有> = n + 2個節點，什麼是矛盾。

對於算法，找到任何路徑並查看未使用路徑節點連接到一個（或多個）子圖的位置就足夠了。詳細內容如下：

如果s僅連接到我們正在尋找的節點以外的一個節點。
如果不是，從s使BFS
查找路徑ST
查找節點連接至S不使用邊緣從ST路徑的節點去
的路徑第一最後節點在連接部分爲節點我們尋找。

來源

2013-10-04 16:08:52 Ante

我可能會誤解這個問題，但它看起來像問題要求證明每個路徑都有一個單一節點共享，而您證明了每對路徑都共享至少1個節點（但不一定是同一個節點）。 – gms7777

不完全。這證明找不到至少有一個節點的2條路徑是不可能的。這意味着（至少）存在（至少）一個節點，該刪除將（至少）2個部分中的圖斷開連接，並且s和t處於不同的部分。證明不是建設性的，而是存在的。對於有建設性的證明，我們需要一個算法:-) – Ante

啊，我現在已經發現了你的邏輯。我會將其添加到您的原始答案中，因爲現在您的證據似乎不完整。 – gms7777

回答

相關問題