木の直径を求めるアルゴリズムの証明

非負の距離（重み）を持つ無向の木について，最も遠い頂点間の距離（最遠頂点間距離）を木の直径という．この直径を求めるアルゴリズムは意外と簡単だが，参考サイトの証明ではすっきりできなかったので，自分なりに証明を考えてみる．

参考サイト：http://www.prefield.com/algorithm/graph/tree_diameter.html

＜アルゴリズムの説明＞
適当な頂点sを選び，sからの最遠頂点uを探索する．次にuからの最遠頂点vを探索する．このとき，(u,v)は木の最遠頂点対となっており，木の直径はuとvの距離と等しい．

＜自分なりの証明＞
uが少なくとも一つの最遠頂点対に含まれることを証明する．基本的な方針は参考サイトと同じ．サイトで理解できなかったところを自分なりに考える．

s：任意の頂点
u：sからの最遠頂点
(x,y)：とある最遠頂点対
t：sからuに向かう経路でuとxが分かれる点
d(a,b)：点aと点bの距離．d(a,b) = d(b,a) >= 0，d(a,a) = 0

図で表すとこんな感じ

yの位置ごとに場合分けして，d(x,y) = d(u,y) または d(x,y) = d(x,u) を示す．

（1）yがs-t間
yがs-t経路上の頂点，またはs-t経路上の頂点から出ている場合．

d(x,y) = d(y,t) + d(t,x) >= d(y,u) = d(y,t) + d(t,u)より
d(t,x) >= d(t,u)
また，d(s,u) = d(s,t) + d(t,u) >= d(s,x) = d(s,t) + d(t,x)より
d(t,u) >= d(t,x)
よって，d(t,x) = d(t,u)となるので，
d(x,y) = d(y,t) + d(t,x) = d(y,t) + d(t,u) = d(u,y)

（2）yがt-x間
yがt-x経路上の頂点，またはt-x経路上の頂点から出ている場合．

tからxに向かう経路でxとyが分かれる点をt'（yがt-x経路上にある場合はt'=y）とすると，
d(x,y) = d(y,t') + d(t',x) >= d(u,y) = d(y,t') + d(t',u)より
d(t',x) >= d(t,t') + d(t,u) (= d(t',u)) …①
また，d(s,u) = d(s,t) + d(t,u) >= d(s,x) = d(s,t) + d(t,x)より
d(t,u) >= d(t,t') + d(t',x) (= d(t,x)) …②
①式と②式の両辺を足し合わせて整理すると，
d(t,t') <= 0
距離は非負より，d(t,t') = 0
よって①式は
d(t',x) >= d(t,u)
②式は
d(t,u) >= d(t',x)
となるので
d(t',x) = d(t,u) = d(t,t') + d(t,u) = d(t',u)
以上より
d(x,y) = d(y,t') + d(t',x) = d(y,t') + d(t',u) = d(u,y)

（3）yがt-u間
yがt-u経路上の頂点，またはt-u経路上の頂点から出ている場合．

tからuに向かう経路でuとyが分かれる点をt'とすると，
d(x,y) = d(x,t') + d(t',y) >= d(x,u) = d(x,t') + d(t',u)より
d(t',y) >= d(t',u)
また，d(s,u) = d(s,t') + d(t',u) >= d(s,y) = d(s,t') + d(t',y)より
d(t',u) >= d(t',y)
よって，d(t',y) = d(t',u)となるので，
d(x,y) = d(x,t') + d(t',y) = d(x,t') + d(t',u) = d(x,u)

以上より，uは最遠頂点対に含まれるので，uの最遠点をvとすると(u,v)は最遠頂点対となる．

＜感想＞
図を見せながらやれば，割と簡単に他人に説明できそうだが，言葉で説明するのは結構めんどくさい．もっとエレガントな証明があるはずだが，自分的にはすっきりしたので良しとする．

何か変なところや，わからんところがあったら，コメントお願いします．