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

木の直径を求めるアルゴリズムの正当性を確認する必要に迫られたため証明した。おまけで最遠点対の総数を求める{O(|V|)}アルゴリズムを発見したので書いておいた。

準備

とりあえず4つ概念を導入しておく。

  • 最遠距離:頂点vから最も遠い点との距離。e(v)=max{d(v,w):w∈V}
  • 木の半径:最遠距離の最小値。min{e(v):v∈V}
  • 木の中心:最遠距離を最小にする点。
  • :vと根とする木で、vからの距離が最大の点

(底は造語。正しいグラフ理論の言葉とかあるんだろうか)

木の中心に関して、以下の定理が成り立つ。

定理:木の中心は隣接している。

定理:木の中心は高々2個。

 この2つを用いて次の定理が導ける。

定理:最遠点対を結ぶパスは木の中心をすべて通る。

しかしこれでは応用が効かないため、最遠点対の位置を特定するより強い定理を証明する。

木の中心が1個のとき

木の中心を根とすると下のような木になる。

f:id:pekempey:20151102215438p:plain

定理:木の半径をRとしたとき、高さR以上の部分木は存在しない。

証明:高さR以上の部分木が存在すると、中心からの距離がR+1以上となる点が存在することになり矛盾する。

定理:木の半径をRとしたとき、高さR-1の部分木が少なくとも2個ある。

証明:(1) 高さR-1の部分木が0個のとき、(2) 高さR-1の部分木が1個のとき矛盾が生じることを示す。

(1) 高さR-1の部分木が0個のとき

中心から距離がRの点が存在しなくなる。(下図参考)

f:id:pekempey:20151102220312p:plain

(2) 高さR-1の部分木が1個のとき

高さR-1の部分木の根vに注目する。高さR-2の部分木があるとき、下図のような経路が存在するためvの最遠距離はRだが、中心が2個あることになってしまい前提に反する。次にR-2の部分木がひとつもないとき、vの最遠距離がR-1以下になり矛盾する。

f:id:pekempey:20151102222605p:plain

よって高さR-1の部分木は少なくとも2つある。

 

さて高さR-1の部分木が2つあるから下図のように、それぞれの部分木の底2つを選ぶと距離2Rの最遠点対が作れる。ちなみに同じ部分木に含まれる2点は最遠点対に成り得ない。なぜならその2点の距離はたかだか2R-2だからである。

f:id:pekempey:20151103141039p:plain

よって中心が1個のときの最遠点対の位置を特定する定理が得られた。

定理:最遠点対は高さR-1の異なる部分木の底のペアである。

木の中心が2個のとき

木の中心を上に書けば、下のような木になる。

f:id:pekempey:20151102231223p:plain

定理:高さR-1以上の部分木は存在しない。

証明:高さR-1以上の部分木が存在した場合、中心からの距離がR+1以上の点が存在することになり矛盾する。

定理:それぞれの中心に対して、少なくとも1つ高さR-2の部分木がある。

証明:高さR-3の部分木しかないと距離がRの点がなくなってしまう。よって必ず高さR-2の部分木がある。

 

下図のような点対を考えると距離2R-1で最遠点対になる。ちなみに片方の中心しか通らないような点対の距離は高々2R-2だから、必ず両方の中心を通ることが示せたことになる。

f:id:pekempey:20151102233755p:plain

ここで、中心同士を繋ぐ辺を切った時できる2つの木をそれぞれ左側の木右側の木と呼ぶことにする。中心が2個のときの最遠点対の位置を特定する定理が以下のものである。

定理:最遠点対は左側の木の底と右側の木の底の対である。

アルゴリズムの正当性の証明

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

  1. 適当な点u∈Vを持ってくる
  2. uから最も遠い点vを見つける
  3. vから最も遠い点wを見つける

というものだった。正当性を考えるために以下の2つの定理を示す。

定理1:u-vパスは中心を通る。

証明:(1)中心が1個のとき

一旦、中心まであがって高さR-1の部分木を下りるのが最も距離を稼げる。

(2)中心が2個のとき

一旦、中心まで上がって反対側の木を降りるのが最も距離を稼げる。

(3)uが中心のとき

反対側の中心に移動して高さR-2の部分木を降りるのが最も距離を稼げる

定理2:vは高さ最大の部分木の底である。

証明:定理1の証明過程より明らか

vが底に落ちてくれて、wも底に落ちるので(v,w)は最遠点対になっている。よってアルゴリズムは正しく動く。

木の中心を求めるアルゴリズム

中心の個数、半径は簡単に求められる。まず中心の個数は直径の偶奇を見ればわかる。半径も直径から分かる。そしてこの2つを使えば中心も求められる。

(1)中心が1個のとき

vからの距離がR、かつwからの距離がRの点が中心になる。

(2)中心が2個のとき

vからの距離がR、かつwからの距離がR-1の点が一つ目の中心。vからの距離がR-1、かつwからの距離がRの点が二つ目の中心。{O(|V|)}

最遠点対の総数を求めるアルゴリズム

(1)中心が1個のとき

それぞれの部分木の底の数{a,b,c,d}を求めていき、{ab+ac+ad+bc+bd+cd=( (a+b+c+d)^2-(a^2+b^2+c^2+d^2) )/2}を計算すればいい。

(2)中心が2個のとき

左側の木の底の数と右側の木の底の数を掛けあわせればいい。

コメント

u,v,wの位置関係が直感的に分かっていい感じ。

ちなみに必要に迫られたのはこの問題↓

pekempey.hatenablog.com