Search on the blog

2016年9月19日月曜日

木の半径、直径、中心、重心

最近よく見聞きする木の用語を整理しておく。

離心数(eccentricity)
節点vから最も離れた節点をwとする。
このときパス(v, w)の長さをvの離心数と呼ぶ。
記号で表すときは、ε(v)と書く。

木の半径(radius)
離心数の最小値。つまりmin_(v ∈ V) ε(v)。
木の中心から最も遠い節点までの距離とも言える。

木の直径(diameter)
離心数の最大値。つまりmax_(v ∈ V) ε(v)。
最も遠い2点間の距離と言える。

木の中心(center)
離心数が最小の節点。
最も離れたところにある節点までの距離が最小の節点なので、なんとなくグラフの中心にありそうなイメージと合致する。

木の重心(centroid)
節点vを根とした木を考える。
vの直接の子以下の最大部分木の節点数が最小となる場合、vを木の重心と呼ぶ。
木を再帰的に分割して何か処理をしたい場合、木の重心で分割すると偏りが少ないため再帰の深さが浅くなるというメリットがある。

以下に木のサンプル図を示す。
節点の中の数字は離心数を表す。木の半径 = 2、直径は4である。
また中心は1つ、重心は2つ存在する。


0 件のコメント:

コメントを投稿