GraphのCentroid

前回解いたCodeforcesの問題のEditorialにcentroidという言葉があったので、調べてみた。

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である。
なるほど、簡単にいくつかパターンを考えてみたけど上記が成り立ちそうだ。

参考サイト

[1] Triangle Medians and Centroids
[2] GRAPH THEORYand APPLICATIONS
[3] Graph Theory