\( \newcommand{\ord}[1]{\mathcal{O}\left(#1\right)} \newcommand{\abs}[1]{\lvert #1 \rvert} \newcommand{\floor}[1]{\lfloor #1 \rfloor} \newcommand{\ceil}[1]{\lceil #1 \rceil} \newcommand{\opord}{\operatorname{\mathcal{O}}} \newcommand{\argmax}{\operatorname{arg\,max}} \newcommand{\str}[1]{\texttt{"#1"}} \)

2016年8月5日 星期五

[ tree centroid ] 樹重心

一棵無向樹\(T=(V,E)\),定義:
\(w_v(u)\)為點\(u\)的權重,\(u \in V\)
\(w_e(e)\)為邊\(e\)的權重,\(e \in E\)
\(d(u,v)\)為\(u\)到\(v\)路徑的權重和,\(u,v \in V\)

重心的定義是:
以這個點為根,那麼所有的子樹(不算整個樹自身)的大小都不超過整個樹大小的一半
即為最大的子樹最小的點

廣義的樹的重心:
無向樹\(T=(V,E)\)滿足
 \(w_v(u)≧0, \; \forall u \in V \)
 \(w_e(e)>0, \; \forall e \in E \)

\(c(u)=\sum_{v \in V}d(u,v)*w_v(v)\)
則樹重心 \(tree \; centroid=u \; | \; min(\{c(u):u \in V\})\)


 \(w_v(u)=1, \; \forall u \in V \)
 \(w_e(e)=1, \; \forall e \in E \)
的情況下,就是一般的樹重心

性質:
  1. 把兩個樹通過一條邊相連得到一個新的樹,那麼新的樹的重心在連接原來兩個樹的重心的路徑上。
  2. 把一個樹添加或刪除一個葉子,那麼它的重心最多只移動一條邊的距離。
用途:
樹分治、動態求樹重心等

可以利用DFS找出最大的子樹最小的點,即為樹重心
樹重心求法(用vector存無向樹):

沒有留言:

張貼留言