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

2020年3月13日グラフグラフ, , 競プロ, 無向グラフ, 重み付きグラフ, 木の直径

木に存在する2つノード間の最大距離を木の直径と言います。

重み無しの木でも、重み付きの木でも、木の最遠頂点間の距離が直径になります。

重み無しの木の例:

以下は直径が5となる木の例です。

6-3-1-0-2-5 を結ぶパスを見ると頂点数は6つで距離は 5 になっています。

直径は頂点5と頂点6を結ぶパスの距離で 5

※ 木の2つの葉(末端にある頂点)を結ぶパス中に含まれる頂点数で最大の数を木の直径とする場合もあります。 上の図では 6 となります。

重み付きの木の例:

以下の重み付き木の場合は、4-1-0-2-5 を結ぶパスの距離で 25 になっています。

頂点 4 と頂点 5 の間の距離が直径でこの場合は 25

アルゴリズム

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

  1. 任意の頂点 s を選ぶ
  2. s から DFS/BFS によって、最も遠くにある頂点 u を探索する
  3. u から DFS/BFS によって、最も遠くにある頂点 v を探索する
  4. u と v を結ぶパスが直径となる

※ 辺の重みを全て 1 とすれば、重み無し木の直径を求めることになります。
※ 「どの頂点から始めても、最も遠くにある頂点 x は直径の端点になる」という事実を利用しています。

計算量

  • \(O(N)\)

頂点数を N とした時を考えます。木の辺の数は N-1 なので、DFSまたはBFSには \(O(N)\) だけかかります。この探索を2回行うので、全体としては \(O(N)\)です。

C++ での実装例

アルゴリズムの正当性

このアルゴリズムの重要なポイントは以下の事実です。

  • どの頂点から始めても、最も遠くにある頂点 x は直径の端点になる

これが成立すれば、適当な頂点 s に対して最も遠くにある点 u は直径の一方の端点になり、u に対して最も遠くにある点 v はもう一方の端点になるはずです。

以下で簡単な証明をしますが、難しければ飛ばしても構いません。

背理法で証明

厳密ではありませんが、簡単に証明を考えてみましょう。

「根 r から最も遠くにある頂点 x は直径の端点にならない」と仮定して矛盾を示すことを考えます。直径の端点をu, v とします。rからx へのパスが直径と最初に交わる点が存在すればそれを h とします。

  1. h が存在する時
    • 「r → h → x 」となるパスがあります。この時 h から最も遠くにある点を考えると h は直径上にあるので本来は u or v になるはずです。しかし「根 r から最も遠くにある頂点は x 」なので x は u または v となってしまい矛盾が生じます。
  2. h が存在しない時
    • 以下の式から、xを端点とする直径を構成することができるので矛盾が生じます。
      \begin{align}
      dist(r, x) &\geq dist(r, h) + \max( dist(u, h), dist(v, h)) \\
      \Rightarrow dist(h, x) &\geq \max( dist(u, h), dist(v, h))
      \end{align}

練習問題