正確性證明：圖論中樹的直徑算法

Question

爲了找到樹的直徑，我可以從樹中取任何節點，執行BFS以找到距離它最遠的節點，然後執行BFS在該節點上。距第二個BFS最遠的距離將產生直徑。

雖然我不確定如何證明這一點？我曾嘗試在節點數量上使用歸納，但情況太多。

任何想法，將不勝感激......

Answer 1

我們稱之爲第一BFS X中發現的端點。關鍵的一步是證明在第一步中發現的x總是「有效」 - 也就是說，它始終處於某條最長路徑的一端。 （請注意，一般情況下，可能有多條同樣最長的路徑。）如果我們可以建立這個路徑，可以很容易地看到以x爲根的BFS將盡可能地從x找到一些節點，因此它必須是一個整體最長的路徑。

提示：假設（相反）在兩個頂點u和v之間存在較長的路徑，它們都不是x。

注意到，在u和v之間的唯一路徑上，必須有一些最高（最接近根）頂點h。有兩種可能性：h從BFS的根到x的路徑上，或者不是。通過顯示在兩種情況下，u-v路徑至少可以通過用x的路徑替換其中的某個路徑段而形成矛盾。

[編輯]實際上，可能沒有必要分別處理這兩種情況。但是我經常發現把配置分解成幾個（或者甚至很多）情況並且分別處理每個配置更容易。這裏，h在從BFS根到x的路徑上的情況更容易處理，並給出了另一種情況的線索。

[編輯2]說回這個以後，現在看來，我認爲這兩種情況需要考慮是：（i）紫外線路徑貫穿從根x的路徑（在一些頂點y，不一定在uv路徑的最高點h）;和（ii）它沒有。我們仍然需要h來證明每個案例。

Answer 2

我要去努力j_random_hacker's hint。讓s, t成爲最遠的一對。令u爲任意頂點。我們有像

u 
    | 
    | 
    | 
    x 
/\ 
/ \ 
/ \ 
s  t , 

一個示意圖，其中x是s, t, u交界處。

假設v是與u最大距離的頂點。如果原理圖現在看起來像

u 
    | 
    | 
    | 
    x v 
/\/
/ * 
/ \ 
s  t , 

然後

d(s, t) = d(s, x) + d(x, t) <= d(s, x) + d(x, v) = d(s, v), 

在不等式成立，因爲d(u, t) = d(u, x) + d(x, t)和d(u, v) = d(u, x) + d(x, v)。存在v在s和x之間而不是在x和t之間的對稱情況。

另一種情況看起來像

u 
    | 
    *---v 
    | 
    x 
/\ 
/ \ 
/ \ 
s  t . 

現在，

d(u, s) <= d(u, v) <= d(u, x) + d(x, v) 
d(u, t) <= d(u, v) <= d(u, x) + d(x, v) 

d(s, t) = d(s, x) + d(x, t) 
     = d(u, s) + d(u, t) - 2 d(u, x) 
     <= 2 d(x, v) 

2 d(s, t) <= d(s, t) + 2 d(x, v) 
      = d(s, x) + d(x, v) + d(v, x) + d(x, t) 
      = d(v, s) + d(v, t), 

所以通過平均化參數max(d(v, s), d(v, t)) >= d(s, t)，並v屬於最大限度遙遠對。

Answer 3

下面看它的另一種方法：

假設ģ =（V，È）是一個非空，與頂點有限樹設置V和邊緣套E。

考慮下面的算法：

1. 讓計數 = 0讓所有邊緣ë最初是無色的。讓C最初等於V。
2. 考慮子集V '的包含所有頂點正好與一個未着色的邊緣V：
   • 如果V' 是空的，然後讓d = 計數 * 2，並停止。
   • 如果V'正好包含兩個元素然後上色他們相互（未着色的）邊緣綠色，讓d = 計數 * 2 + 1，並停止。
   • 否則，V'包含至少三個頂點;進行如下：
3. 遞增計數一個。
4. 從刪除所有頂點C沒有無色邊緣。
5. 對於具有兩個或更多未着色邊緣的每個頂點，將其每個綠色邊緣重新着色爲紅色（某些頂點可能具有零這樣的邊緣）。
6. 對於每個頂點V'，將其無色邊緣變爲綠色。
7. 返回步驟（2）。

這基本上是從葉子向內着色的圖形，用綠色標記與葉子最大距離的路徑，並標記只有較短距離爲紅色的路徑。同時，Ç，中心，具有較短的最大距離到葉節點被縮減距離，直到Ç僅包含與對葉的最大的最大距離的一個或兩個節點。通過構造，從葉頂點到它們最近的僅穿過綠色邊緣的中心頂點的所有簡單路徑長度相同（計數），以及從葉頂點到其最近中心頂點的所有其他簡單路徑（遍歷在至少一個紅色邊緣）更短。此外可以證明，

• 該算法總是給出的條件下終止，留下的ģ每個邊沿染成紅色或綠色，並留下Ç與一個或兩個元件。
• 在算法終止，d是ģ直徑，在邊緣測量的。
• 給定一個頂點v在V，在ģ最大長度簡單路徑起始於v正是那些含有包含中心的所有頂點，終止於葉，並只遍歷中心和遠端點之間的綠色邊緣。這些從中心到離中心最遠的一片離開v。

---

現在考慮你的算法，這可能是更實用，在上面的光。從任何一個頂點v開始，恰好有一個簡單的路徑p從頂點，在中心頂點結束，幷包含中心的所有頂點（因爲摹是一棵樹，如果有是兩個頂點C然後它們共享邊緣）。可以示出具有v作爲一個端點都具有p的並集與從中心到葉片遍歷僅綠色邊緣的簡單路徑的形式中ģ最大簡單路徑。

我們的目的的關鍵點是另一端點的輸入邊緣必然是綠色的。因此，當我們搜索從那裏開始的最長路徑時，我們可以訪問那些僅遍歷從葉中心（所有頂點）到另一葉的綠色邊的人。這些正是G中的最大長度簡單路徑，所以我們可以確信第二次搜索確實會揭示圖形直徑。