centroidっていうのは重心のことで、三角形の重心もcentroid[1]と呼ばれる。
定義
ある節点vから派生するすべての部分グラフを考える。それぞれの部分グラフに含まれる枝の数をそれぞれe1, e2, e3, ..とすると、max eiを節点vのweightと呼ぶ。
weightが最小の節点vをグラフのcentroidと呼ぶ[2]。
木の場合は、上の「部分グラフに含まれる枝の数」を「部分グラフに含まれる節点の数」と置き換えてもよいです。
特徴
で、Centroidには以下の面白い特徴[3]がある。
「節点数Nの木を考える。節点vがcentroidであるとき、weight(v) <= N/2が成り立つ。」
特にcentroidが一つだけ存在する場合は、weight(v) <= (N-1)/2となる。（centroidal）
centroidが複数個ある場合は、隣接する頂点v, wが存在しweight(v) = weight(w) = N/2となる。（bicentroidal）
すべての木は、centroidalかbicentroidalである。
なるほど、簡単にいくつかパターンを考えてみたけど上記が成り立ちそうだ。
「節点数Nの木を考える。節点vがcentroidであるとき、weight(v) <= N/2が成り立つ。」
特にcentroidが一つだけ存在する場合は、weight(v) <= (N-1)/2となる。（centroidal）
centroidが複数個ある場合は、隣接する頂点v, wが存在しweight(v) = weight(w) = N/2となる。（bicentroidal）
すべての木は、centroidalかbicentroidalである。
なるほど、簡単にいくつかパターンを考えてみたけど上記が成り立ちそうだ。
参考サイト
[1] Triangle Medians and Centroids[2] GRAPH THEORYand APPLICATIONS
[3] Graph Theory
0 件のコメント:
コメントを投稿