# 圖論演算法

## 1.Counting # Spanning Tree
- 在 $K_n$ 中的 Spanning Tree 數量為 $n^{n-2}$，可以和 Prufer sequence 一一對應。
- Tree to sequence
- 
- Sequence to Tree
- 
- General Graph 中的 Spanning Tree 數量，滿足遞迴關係 $n(G)=n(G\setminus e)+n(G-e)$
## 2.Minumum Spanning Tree
- **Boruvka’s Algorithm** ： $O(mlogn)$
- 
- **Prim’s Algorithm** ：
- 
- 找所有的邊最小的：$O(mn)$
- Binary Heap：$O(mlogn)$
- Fibonacci Heap：$O(m+nlogn)$
- **Kruskal’s Algorithm** ： 用disjoint set ，$O(mlogn)$
- 
- **Hybrid Algorithm** ： $O(mloglogn)$
- 先跑 Boruvka’s Algorithm $O(loglogn)$ 次. $~~\text{Time} = O(mloglogn)$
- 再跑 Prim Algorithm 對剩下 $n/logn$ 點. $~~\text{Time} = O(m+n)$
- 其他 Algorithm ：
- $O(m\beta(m,n))$ Fredman-Tarjan (1987)
- $O(mlog\beta(m,n))$ Gabow-Galil-Spencer-Tarjan (1986)
- $O(m\alpha(m,n))$ Chazelle (JACM 2000)
## 3.Shortest Path Tree ： **以下討論對象，基本上是有向圖，無負環**
- **Dijkstra Algorithm** ： 無負邊才可以使用
- 
- 找所有的點最小的：$O(n^2)$
- Binary Heap：$O(mlogn)$
- Fibonacci Heap：$O(m+nlogn)$
- **Bellman-Ford Algorithm** ： relax $n-1$ 次，並檢測有無負環，$O(mn)$
- 
- **Lawler Algorithm** ： 無環 → 照 topologic order → $O(m+n)$
## All pair shortest path：
- **Floyd-Warshall Algorithm** ： $O(n^3)$
- 
- 設 $D_{i,j,k}$ 為從 $i$ 到 $j$ 只以 $\{1...k\}$ 為中間節點的最短路徑的長度。
- 若最短路徑經過點 $k$，則 $D_{i,j,k}=D_{i,k,k-1}+D_{k,j,k-1}$
- 若最短路徑不經過點 $k$，則 $D_{i,j,k}=D_{i,j,k-1}$
- **Johnson’s reweighting Algorithm** ： $O(mn)+O(mn+n^2logn)$
- 1.用 Bellman-Ford 演算法，使圖沒有負邊
- $w'=w+h(i)-h(j)$
- 2.對每個點使用 Fibonacci Heap 版本的 Dijkstra Algorithm
## 4.1 Minimum Routing Cost Spanning Tree (ratio = 2)
- General Graph 的 MRCT 問題是 NP-hard → **近似演算法**
- **Solution decomposition**
- 有時候我們設計演算法時，會依賴最佳解的一部分，來達到 approximation 的設計
- 最佳解的 Centroid 的 SPT ，是一個 2-approximation。
- 最佳解的 1/3 separator 兩端 SP 所構成的 star，是一個 15/8-approximation。
- 最佳解的 1/3 separator 的 path 所構成的 star，是一個 3/2-approximation。
- 最佳解的 1/4 separator 的 fork 所構成的 star，是一個 4/3-approximation。
- 我們雖然沒有最佳解，但有機會得到**對應的結構**：
- polynomial time 找到近似解，保證和最佳解相差一個 ratio。
- exponential time 得到近似解，不如直接爆搜最佳解就好。
- 一些定義與性質：
- 定義 ： $C(T)=\sum\limits_{u,v} d_T(u,v)$
- 給定 tree $T$ ，根據三角不等式：$~~~~\sum\limits_{u,v}d_T(u,v)\\\le\sum\limits_{u,v}d_T(S,u)+d_T(S,v)\\\le2n\sum\limits_{v}d_T(S,v)$
- 如果 $r$ 是 $G$ 的 Median：$n\sum\limits_vd_G(r,v)\le\sum\limits_{u,v}d_G(u,v)$。
- 如果 $x$ 是 $T$ 的 Centroid：$d_T(x,v)$ 會被算超過 $\frac{n}{2}+\frac{n}{2}$ 次。
- 每個 median 的 SPT routing cost 可能不相同，但都不會超過兩倍
- 可以舉出例子，使得 median 的 SPT routing cost，接近最佳解的兩倍
- 樹的 Centroid = 樹的 Median
- **$G$ 的 Median $r$ 的 shortest path tree $Y$ 是原圖 MRCT 的 2-approximation.**
- $C(\hat{T})\\\ge\sum\limits_{u,v} d_G(u,v)\\\ge n\sum\limits_vd_G(r,v)~~\text{//median 的性質}$
- $C(Y)\\\le \sum\limits_{u,v}[d_Y(u,r)+d_Y(r,v)]~~\text{//三角不等式展開}\\=2n\sum\limits_vd_Y(r,v)\\=2n\sum\limits_vd_G(r,v)~~\text{//Y 是 r 的 shortest path tree}$
- **$\hat{T}$ 的 Centroid $x$ 的 shortest path tree $Z$ 是原圖 MRCT 的 2-approximation.**
- $C(\hat{T})\\\ge n\sum\limits_vd_\hat{T}(x,v)~~\text{//每個邊至少被算 n 次}\\\ge n\sum\limits_vd_G(x,v)$

## 4.2 Minimum Routing Cost Spanning Tree (ratio = 15/8, 3/2, 4/3+ϵ)
- 一些例子與性質：
- $δ$-separator 的任何一個 branch 的點個數不超過 $δ\cdot|V(T)|$。
- Centroid 是 Minimal $1/2$-separator。
- 一棵 Tree 的 Minimal $1/3$-separator，必定是包含 centroid 的一條 path。
- 一棵 Tree 的 Minimal $1/4$-Separator ，必定是包含 centroid 的一個 fork。
- $\delta$-separator 上的任何一個 edge e
- 兩端點數都會 $>\delta n$ (反證、建構的性質)
- $l(e)\ge2\delta(1-\delta)n^2$
- 前提：
- $S$ 是 $\hat{T}$ 的最小 $\delta$-separator，$Y\in star(S)$
- $X$ 是任意 subtree，$Z\in star(X)$
- **已知 $S$ 的情況下，存在演算法得到 $4/3$ 的近似解：**
- **Lemma 2**：$C(Z)\le 2n\sum\limits_vd_G(v,X)+\frac{n^2}{2}w(X)$
- 第一項：每個邊最多算 2n 次
- 第二項：routing load 本身上限是 $n^2/2$
- **Lemma 3**：$C(\hat{T})\ge 2(1-\delta)n\sum\limits_vd_\hat{T}(v,S)+2\delta(1-\delta)n^2w(S)$
- 第一項：每個邊至少算 $2(1-\delta)n$ 次
- 第二項：因為兩端點數至少 $\delta n$，因此下限是 $2\delta(1-\delta)n^2$
- $\text{ratio}=\frac{C(Y)}{C(\hat T)}=\max(\frac{1}{1-\delta},\frac{1}{4\delta(1-\delta)})=4/3~~~$
- **最佳解的 1/3 separator 其中兩點 SP 的 star，是一個 15/8-approximation。**
- $C(\hat{T})\ge\frac{4n}{3}\sum\limits_vd_\hat{T}(v,S)~+~\frac{4n^2}{9}w(S)$
- $C(Z)$$\le2n\sum\limits_vd_G(v,X)~+~\frac{n^2}{2}w(X)\\\le2n\sum\limits_vd_\hat{T}(v,S)~+~\frac{5n^2}{6}w(S)~~(~\sum\limits_vd_G(v,X)\le\sum\limits_vd_\hat{T}(v,S)+\frac{n}{6}w(S)~)$
- 因為至少有 $2/3$ 個點在 $G$ 裡，滿足：
- $v\in G$ ： $d_G(v,X)\le d_\hat{T}(v,S)$
- $v\notin G$ ： $d_G(v,X)\le d_\hat{T}(v,S)+\frac{1}{2}w(S)$
- **(不可行)最佳解的 1/3 separator 的 path 所構成的 star，是一個 3/2-approximation。**
- $C(\hat{T})\ge\frac{4n}{3}\sum\limits_vd_\hat{T}(v,S)~+~\frac{4n^2}{9}w(S)$
- $C(Y)\le2n\sum\limits_vd_G(v,S)~+~\frac{n^2}{2}w(S)$
- **最佳解的 1/3 separator 其中三點 SP 的 star，是一個 3/2-approximation。**
- $C(\hat{T})\ge\frac{4n}{3}\sum\limits_vd_\hat{T}(v,S)~+~\frac{4n^2}{9}w(S)$
- $C(Z)$$\le2n\sum\limits_vd_G(v,X)~+~\frac{n^2}{2}w(X)\\\le2n\sum\limits_vd_\hat{T}(v,S)~+~\frac{2n^2}{3}w(S)~~(~\sum\limits_vd_G(v,X)\le\sum\limits_vd_\hat{T}(v,S)+\frac{n}{12}w(S)~)$
- 令 $S=(p_1,p_2,...,p_k)$，其中 $p_q$ 是 centroid
- $v\in V_1\cup V_q\cup V_k$ ： $d_G(v,X)\le d_\hat{T}(v,S)$
- $v\in \cup_{1<i<q}V_i$ ： $d_G(v,X)\le d_\hat{T}(v,S)+\frac{1}{2}d_\hat{T}(p_1,p_q)$
- $v\in \cup_{q<i<k}V_i$ ： $d_G(v,X)\le d_\hat{T}(v,S)+\frac{1}{2}d_\hat{T}(p_q,p_k)$
- **(不可行)最佳解的 1/4 separator 的 fork 所構成的 star，是一個 4/3-approximation。**
- $C(\hat{T})\ge\frac{3n}{2}\sum\limits_vd_\hat{T}(v,S)~+~\frac{3n^2}{8}w(S)$
- $C(Y)\le2n\sum\limits_vd_G(v,S)~+~\frac{n^2}{2}w(S)$
- **最佳解的 1/4 separator 其中 $k$ 點 SP 的 star，是一個 4/3+ϵ-approximation。**
- $C(\hat{T})\ge\frac{3n}{2}\sum\limits_vd_\hat{T}(v,S)~+~\frac{3n^2}{8}w(S)$
- $C(Z)$$\le 2n\sum\limits_vd_G(v,X)+\frac{n^2}{2}w(X)\\\le 2n\sum\limits_vd_{\hat T}(v,S)+2n\cdot\Delta n\cdot\frac{1}{2}w(S)+\frac{n^2}{2}w(S)\\\le 2n\sum\limits_vd_{\hat T}(v,S)+(\frac{1}{2}+\Delta)n^2w(S)$
- 我們總是可以取夠多的點使得，最佳解的 partion 每一部分點數都 $<\Delta n$
- 每一部分的點數都 $<n/8$，則要多取 $1$ 個點
- 每一部分的點數都 $<n/32$，則要多取 $7$ 個點
## 4.3 Minimum Routing Cost Spanning Tree (ratio = 1+ϵ)
- **Metric Closure**
- $\bar{G}$ 是 $G$ 的 Metric Closure
- 1.$\bar{G}$ 是 complete graph
- 2.$\bar{w}(u,v)=d_G(u,v)$
- Bad Edge $(a,b)$：
- $(a,b)\notin G$
- $\bar{w}(a,b)<w(a,b)$
- $C(mrct(\bar{G}))\le C(mrct(G))$
- 因為每一個 $mrct(G)$ 上的邊 $(a,b)$，$\bar{w}(a,b)\le w(a,b)$
- $C(mrct(\bar{G}))\ge C(mrct(G))$
- 
- 給定 $\bar{G}$ 上有 bad edge 的 spanning tree，把他轉成 $\bar{G}$ 上沒有 bad edge。
- 一些關係：
- $T$ 是 $\bar{G}$ 上由 $a$ rooted 的一棵 tree
- $(a,b)$ 是 $T$ 上的一個 bad edge
- $SP_G(a,b)=(a,x,...,b)$
- $y$ 是 $x$ 的 parent
- 如果 $x$ 在其他子樹裡：
- $Y^*\leftarrow T \cup(x,b)-(a,b)$
- $Y^{**}\leftarrow Y^* \cup(a,x)-(x,y)$
- 如果 $x$ 是 $b$ 的後代：(看成是 rooted by a，其他論述都相似)
- $Y^*\leftarrow T \cup(a,x)-(a,b)$
- $Y^{**}\leftarrow Y^* \cup(b,x)-(x,y)$
- 證明：
- 
- $U_1=V(T_a)-V(T_b)$
ㄌ - $U_2=V(T_a)-V(T_b)-V(T_x)$
- 如果 $C(Y^*)\le C(T)$，得證。
- 如果 $C(Y^*)> C(T)$：
- 前提：
- $\sum\limits_{u\in U_1}\sum\limits_{v\in V(T_b)}(d_T(u,x)+\bar{w}(x,b))-(d_T(u,a)+\bar{w}(a,b))>0$
- $\sum\limits_{u\in U_1}\sum\limits_{v\in V(T_b)}(d_T(u,x)-d_T(u,a)-\bar{w}(a,x))>0$
- $\sum\limits_{u\in U_1}(d_T(u,x)-d_T(u,a)-\bar{w}(a,x))>0$
- $\sum\limits_{u\in U_1}(d_T(u,x)-d_T(u,a))>|U_1|\bar{w}(a,x)$
- $\sum\limits_{u\in U_2}(d_T(u,x)-d_T(u,a))>|U_1|\bar{w}(a,x)$
- $\sum\limits_{u\in U_2}(d_T(u,a)-d_T(u,x))<-|U_1|\bar{w}(a,x)$
- 因此：
- $\sum\limits_{u\in U_2}\sum\limits_{v\in V(T_x)}(d_T(u,a)+\bar{w}(a,x)-d_T(u,x))+\sum\limits_{u\in V(T_x)}\sum\limits_{v\in V(T_b)}(d_T(u,x)+\bar{w}(x,b)-(d_T(u,a)+\bar{w}(a,b)))$
- $\le\sum\limits_{u\in U_2}\sum\limits_{v\in V(T_x)}(d_T(u,a)+\bar{w}(a,x)-d_T(u,x))$
- $=|V(T_x)|\sum\limits_{u\in U_2}(d_T(u,a)-d_T(u,x)+\bar{w}(a,x))$
- $<|V(T_x)|\cdot(|U_2|-|U_1|)\cdot \bar{w}(a,x)$
- $\le 0$
- 演算法的步驟：
- 先用 $O(mn+n^2logn)$ 時間，把 $G$ 轉成 metric closure $\bar{G}$
- 在 metric closure $\bar{G}$ 上找 $1+\epsilon$ 的 MRCT 近似解
- 花 $O(n^3)$ 時間，轉回原圖 $G$ 上的 MRCT
- **Metric Closure 上的 PTAS 演算法：**
- $k$ star：不超過 $k$ 個 internal node 的 tree
- 一個 $\delta$ separator，可以被拆成數段 $\delta$ path
- $\delta$ path 指說除了頭尾以外的所有點數，總和 $\le\frac{1}{2}\delta n$
- #cut nodes + #leaves $\le\lceil\frac{2}{\delta}\rceil+3$
- 證明：
- $h$：number of leaves
- $h'$：number of degree 3 $\uparrow$ cut nodes
- $h''$：number of additional cut nodes
- $h'\le h-2$
- $h''\le\lceil\frac{n-h\delta n}{\frac{1}{2}\delta n}\rceil-1=\lceil\frac{2}{\delta}\rceil-2h-1$
- $h+h'+h''\le\lceil\frac{2}{\delta}\rceil-3$
- 把 $p^c$ 全部掛到 $u$ 或 $v$，routing cost 也只會是最佳解的 $\frac{1}{1-\delta}$
- 
- $X$ 是 $\delta$-spine
- $X'$ 是把 $(u,v)$ 建一個邊，並把 $p^c$ 所有點掛到 $u$ 上
- $X''$ 是把 $(u,v)$ 建一個邊，並把 $p^c$ 所有點掛到 $v$ 上
- 底下算子結構的 routing cost
- 只看結構不同那些邊的 routing cost 總和
- 每個 routing cost 要考慮原圖的 $p^a,p^b$ 部分的點。
- $經過~path~的~routing ~cost\\=2\sum\limits_{j=1}^l(p^a+p^c-\sum\limits_{k=j}^{l-1}n_k)(p^b+\sum\limits_{k=j}^{l-1}n_k)w(e_j)\\=2(\sum\limits_{j=1}^l(p^a+p^c)p^bw(e_j)+(p^a-p^b)\sum\limits_{j=1}^l\sum\limits_{k=j}^{l-1}n_kw(e_j)+\sum\limits_{j=1}^l(p^c-\sum\limits_{k=j}^{l-1}n_k)\sum\limits_{k=j}^{l-1}n_kw(e_j))\\\ge2((p^a+p^c)p^bw(p)+(p^a-p^b)\sum\limits_{j=1}^{l-1}n_jd_T(u,r_j))$
- $C(X)\\\ge2(1-\delta)n\sum\limits_qd_T(q,p)+2((p^a+p^c)p^bw(p)+(p^a-p^b)\sum\limits_{j=1}^{l-1}n_jd_T(u,r_j))$
- $C(X')\\\le2((p^a+p^c)p^bw(u,v)+(n-1)(\sum\limits_qd_T(q,p)+\sum\limits_{j=1}^{l-1}n_jd_T(u,r_j)))\\\le2(p^ap^bw(p)+n\sum\limits_qd_T(q,p)+p^bp^cw(p)+n\sum\limits_{j=1}^{l-1}n_jd_T(u,r_j))$
- $C(X'')\\\le2((p^b+p^c)p^aw(u,v)+(n-1)(\sum\limits_qd_T(q,p)+\sum\limits_{j=1}^{l-1}n_j(w(p)-d_T(u,r_j)))\\\le2(p^ap^bw(p)+n\sum\limits_qd_T(q,p)+p^ap^cw(p)+np^cw(p)-n\sum\limits_{j=1}^{l-1}n_jd_T(u,r_j))$
- $min(c(X'),c(X''))\\\le2(p^ap^bw(p)+n\sum\limits_qd_T(q,p)\\+\frac{p^a}{p^a+p^b}(p^bp^cw(p)+n\sum\limits_{j=1}^{l-1}n_jd_T(u,r_j))+\frac{p^b}{p^a+p^b}(p^ap^cw(p)+np^cw(p)-n\sum\limits_{j=1}^{l-1}n_jd_T(u,r_j)))\\=2(n\sum\limits_qd_T(q,p)+\frac{w(p)}{p^a+p^b}(p^ap^b(n-p^c)+2p^ap^bp^c+np^bp^c)+\frac{n(p^a-p^b)}{p^a+p^b}\sum\limits_{j=1}^{l-1}n_jd_T(u,r_j))$
- $\frac{min(c(X'),c(X''))}{c(X)}\le max(\frac{1}{1-\delta},\frac{\frac{np^b(p^a+p^c)+p^ap^bp^c}{p^a+p^b}}{(p^a+p^c)p^b},\frac{\frac{n(p^a-p^b)}{p^a+p^b}}{p^a-p^b})=\frac{1}{1-\delta}$
- $\frac{\frac{n(p^a-p^b)}{p^a+p^b}}{p^a-p^b}=\frac{n}{p^a+p^b}\le\frac{n}{n-\frac{1}{2}\delta n}=\frac{1}{1-\frac{1}{2}\delta}\le\frac{1}{1-\delta}$
- $\frac{\frac{np^b(p^a+p^c)+p^ap^bp^c}{p^a+p^b}}{(p^a+p^c)p^b}=\frac{n}{p^a+p^b}+\frac{p^ap^c}{(p^a+p^b)(p^a+p^c)}\\\le\frac{n}{p^a+p^b}+\frac{p^c}{p^a+p^b}=\frac{n+p^c}{p^a+p^b}=\frac{n+p^c}{n-p^c}\le\frac{n+\frac{\delta}{2}n}{n-\frac{\delta}{2}n}=\frac{2+\delta}{2-\delta}\\=1+\frac{2\delta}{2-\delta}=1+\frac{\delta}{1-\frac{\delta}{2}}\le 1+\frac{\delta}{1-\delta}=\frac{1}{1-\delta}$
- 尋找 $k$-star
- $k=\frac{2}{\delta}-3\Rightarrow \delta=\frac{2}{k+3}$
- $\frac{1}{1-\delta}=\frac{1}{1-\frac{2}{k+3}}=\frac{k+3}{k+1}$
- 在 metric graph 下，最好的 $k$-star 搭配最好的掛法所形成的 spanning tree，是 MRCT 最佳解的 $\frac{k+3}{k+1}$-approximation
- 時間複雜度：
- $O(\binom{n}{k}\cdot \binom{n-1}{k-1}\cdot k^{k-2})\cdot O(n^3)=O(n^{2k+2})$
- $O(\binom{n}{k})$：窮舉圖上 $k$ 個點。
- $O(\binom{n-1}{k-1})$：把 $n-k$ 個點掛上去的組態數。
- $O(k^{k-2})$：$k$ 個點的 spanning tree 種類數。
- $O(n^3)$：assingment problem 匈牙利演算法。
## 5.Optimal Sum-Requirement Communication Spanning Trees (SROCT)
- **Optimal Communication Spanning Trees(OCT)**
- 
- PROCT
- $\lambda(u,v)=r(u)r(v)$
- $l(T,r,e)=2\cdot|r(T_u)|\cdot|r(T_v)|$
- SROCT
- $\lambda(u,v)=r(u)+r(v)$
- $l(T,r,e)=2\cdot|r(T_u)|\cdot|V(T_v)|+2\cdot|V(T_u)|\cdot|r(T_v)|$
- **Optimal Sum-Requirement Communication Spanning Trees (SROCT) 的 2-approximation**
- r-centroid：
- 定義 $R=\sum\limits_{v\in V}r(v)$
- r-centroid 的任何一個分支，$r$ 值總和 $\le\frac{R}{2}$
- Path P：
- $T$ 是最佳解
- $x_1$ 是 $T$ 的 centoid
- $x_2$ 是 $T$ 的 r-centoid
- $P=SP_T(x_1,x_2)$
- 最佳解的下限：
- 如果 $e\in P$，則 $l(T,r,e)\ge nR$
- $l(T,r,e)\\=2\cdot|V(T_1)|\cdot|r(T_2)|+2\cdot|r(T_1)|\cdot|V(T_2)|\\=2\cdot|V(T_1)|\cdot|r(T_2)|+2\cdot(R-|r(T_2)|)\cdot(n-|V(T_1)|)\\=2(~2(|V(T_1)|-\frac{n}{2})(|r(T_2)|-\frac{R}{2})+\frac{nR}{2})\\\ge nR$
- 最佳解：
- $C_s(T)\\=\sum\limits_{u,v}(r(u)+r(v))(d_T(u,P)+d_T^P(u,v)+d_T(P,v))\\\ge\sum\limits_{u,v}(r(u)+r(v))(d_T(u,P)+d_T(P,v))+nRw(P)\\\ge\sum\limits_v\sum\limits_{dif~bran}2(r(u)+r(v))d_T(v,P)+nRw(P)\\\ge\sum\limits_v(R+nr(v))d_T(v,P)+nRw(P)$
- 我們找的解的上限：
- 窮舉所有點，每個點找 shortest path tree，並從中找最小值
- 如果 $Y$ 是任意 spanning tree，$x$ 是任意的點
- $C_s(Y)=\sum\limits_{u,v}(r(u)+r(v))d_Y(u,v)\\\le\sum\limits_{u,v}(r(u)+r(v))(d_Y(u,x)+d_Y(x,v))\\=2\sum\limits_{u,v}(r(u)+r(v))d_Y(v,x)\\=2\sum\limits_v\sum\limits_u(r(u)+r(v))d_Y(v,x)\\=2\sum\limits_v(R+nr(v))d_Y(v,x)$
- $Y^*$ 是 centroid $x_1$ 的 shortest path tree
- $C_s(Y^*)\\\le2\sum\limits_v(nr(v)+R)d_{Y^*}(v,x_1)\\\le2\sum\limits_v(nr(v)+R)(d_T(v,P)+w(SP(v,x_1)\cap P))$
- $Y^{**}$ 是 r-centroid $x_2$ 的 shortest path tree
- $C_s(Y^{**})\\\le2\sum\limits_v(nr(v)+R)d_{Y^{**}}(v,x_2)\\\le2\sum\limits_v(nr(v)+R)(d_T(v,P)+w(SP(v,x_2)\cap P))$
- $Y^*$ 和 $Y^{**}$ 的上限：
- $\min(C_S(Y^*),C_S(Y^{**}))\\\le\frac{C_S(Y^*)+C_S(Y^{**})}{2}\\\le2\frac{\sum\limits_v(nr(v)+R)(d_{Y^{**}}(v,x_1)+d_{Y^{**}}(v,x_2))}{2}\\\le\sum\limits_v(nr(v)+R)(2d_T(v,p)+w(p))\\=2\sum\limits_v(nr(v)+R)d_T(v,p)+\sum\limits_v(nr(v)+R)w(p)\\=2\sum\limits_v(nr(v)+R)d_T(v,p)+2nRw(p)\\\le2C_S(T)$
## 6.Diameters of a Tree
- 因為是樹狀結構，距離都是指唯一的最短距離。
- 定義：
- Eccentricity
- 一個點 $u$ 的 eccentricity，定義為它到其他點的最遠距離。
- $D_T(u,V)=\max\limits_{v\in V}d_T(u,v)$
- Diameter
- 一個樹 $T$ 的 diameter，定義為所有 eccentricity 的最大值。
- $\max\limits_{u,v}d_T(u,v)=\max\limits_u\{\max\limits_{v\in V}d_T(u,v)\}$
- Radius
- 一個樹 $T$ 的 diameter，定義為所有 eccentricity 的最小值。
- $\min\limits_u\{\max\limits_{v\in V}d_T(u,v)\}$
- Center
- 最小 eccentricity 的點，稱之為 center。
- Intersection Vertex
- 給定三個點的交會點
- $c(x,y,z)=SP_T(x,y)\cap SP_T(y,z)\cap SP_T(x,z)$
- 觀察與證明：
- 對於 unweighted tree $T$：
- $2\times\text{Radius}-1\le\text{Diameter}\le2\times\text{Radius}$
- 對於 weighted tree $T$：
- $2\times\text{Radius}-w_{max}\le\text{Diameter}\le2\times\text{Radius}$
- $d_T(x,c(x,y,z))=\frac{1}{2}(d_T(x,y)+d_T(x,z)-d_T(y,z))$
- 對任意點來說，Diameter 兩端點必定有一點離自己最遠：
- 如果 $v_1,v_2$ 是 Diameter 兩端點， $r$ 是 diameter 上的任意一點，則
- $d_T(r,x)\le\max\{d_T(r,v_1),d_T(r,v_2)\}$
- 如果 $v_1,v_2$ 是 Diameter 兩端點， $r$ 是 diameter 外的任意一點，則
- 令 $u=c(r,v_1,v_2)$，不失一般性 $d_T(u,v_1)\ge d_T(u,v_2)$
- $d_T(x,r)\le d_T(x,u)+d_T(u,r)\le d_T(v_1,u)+d_T(u,r)\le d_T(v_1,r)$
- 對任意點來說，離自己最遠的點必定是 Diameter 的端點：
- 假設 $v_3$ 是距離 $r$ 最遠的點，$v_1,v_2$ 是 Diameter 兩端點
- 假設 $u_1=c(r,v_1,v_2)$ ，$u_2=c(r,v_1,v_3)$
- 不失一般性，$d_T(u_1,v_1)\ge d_T(u_1,v_2)$
- $d_T(r,v_3)=d_T(r,v_1)\ge d_T(r,v_2)$
- 首先：$u_2$ 必定落在 $SP(v_1,u_1)$ 上
- 否則 $d_T(v_1,v_3)\\=d_T(v_1,u_2)+d_T(u_2,v_3)\\=2d_T(v_1,u_2)\\>2d_T(v_1,u_1)\\\ge d_T(v_1,u_1)+d_T(u_1,v_2)\\=d_T(v_1,v_2)$
- 因此：$d_T(v_3,v_2)=d_T(v_1,v_2)$
- 如果 $v_1,v_2$ 是 Diameter 兩端點，從 $v_1$ 走到 $v_2$ 過程中，$u_1,u_2$ 是 $d_T(x,v_1)$ 是否 $\le\frac{1}{2}w(P)$ 的轉折點，則
- $u_1$ 的 eccentricity 是 $d_T(u_1,v_2)$
- $u_2$ 的 eccentricity 是 $d_T(u_2,v_1)$
- $u_1$ 或是 $u_2$ 有一點為 center。
- 其他點的 eccentricity 都至少是 $d_T(u_1,v_2)$ 或是 $d_T(u_2,v_1)$
- 兩個 Diameter 必定有共同點
- 如果 $v_1,v_2$ 是 Diameter 兩端點，$v_3,v_4$ 是另外一個 Diameter 兩端點
- 令 $u_1=c(v_1,v_2,v_3)$, $u_2=c(v_1,v_3,v_4)$
- $d_T(v_1,v_4)+d_T(v_2,v_3)\ge d_T(v_1,v_2)+d_T(v_3,v_4)+d_T(u_1,u_2)>2\times\text{diameter}$
- 每個 Diameter 必定交於一個共同點
- 演算法：
- 找一個點 $u$ 的 Eccentricity
- $D_T(u,V)=\max\limits_{s~是~u~的小孩}\{D_{T_s}(s,V(T_s))+w(u,s)\}$
- 
- 找一棵樹 $T$ 的 Diameter
- 
- 找一棵樹 $T$ 的 Center、Radius
- 沿著 Diameter 走，直到經過 $\frac{1}{2}w(p)$
## 7.Steiner Minimal Trees
- **Euclidean SMT：**
- 給定二維平面上一些 terminal nodes，找出一個 spanning tree 使得 cost 最小。
- 比較：
- Minimum Spanning Tree：不能用額外的點
- Steiner Minimal Tree：可以用額外的點
- **Gilbert–Pollak Conjecture：**
- $MST/SMT\le\frac{2}{\sqrt{3}}$
- **Rectilinear SMT：**
- 距離定義成 $d(v_1,v_2)=|x_1-x_2|+|y_1-y_2|$
- Rectilinear Distance / Manhattan Distance
- $MST/SMT\le\frac{3}{2}$ (Hwang 1976)
- **Graph SMT：**
- 給定 $G=(V,E,w)$ 以及 $L\subseteq V$ 為 terminals，找一個包含所有 $L$ 的點且 cost 最小的 spaning tree $T$。
- **NP-hard**
- 
- EXACT COVER
- 給定一些 subset of $S=\{u_1,u_2,...,u_n\}$，可否挑出一些 subsets，使得彼此 disjoint 且聯集為 $\{u_1,...,u_n\}$
- STEINER MINIMUM TREE
- 給定 $G=(V,E,w)$ 以及 $L\subseteq V$ 為 terminals，以及 $k$ ，可否找出一個包含所有 $L$ 的點且 cost $\le k$ 的 spaning tree $T$。
- Reduction：
- $S=\{1,2,3,4,5,6,7,8\}$
- $\{1,2,4,5\}~~\{2,3,4\}~~\{6,7,8\}~~\{3,6\}~~\{7,8\}~~\{1,5\}$
- 
- 
- **Approximation**
- 
- $w(T)\le w(T_L)$
- output 其實是把 $T_L$ 的重複邊去重
- $w(T_L)\le w(tsp(G_L))$
- $tsp$ 任意去除一個邊也是 spanning tree
- $w(tsp(G_L))\le w(smt_{tour})$
- $tsp$ 是經過每個點都一次的最低走法
- $w(smt_{tour})= 2w(smt)$
- 定義 $tour$ 為沿著 $smt$ 的走法
## 8.Edge-Partition of a Tree
- **k-split**
- 一個 k-tuple $(T_1,T_2,...,T_k)$ 是 $T$ 的 k-split：
- 1.每一個 $T_i$ 都是 connected
- 2.$T_i$ 和 $T_j$ 彼此間是 edge disjoint
- 3.$T=\cup~T_i$
- **k-split 的 Ratio**
- $ratio=\frac{\max~e(T_i)}{\min~e(T_i)}$
- **2-split 的 ratio 最多為 2 切法**
- 假設樹有 $n$ 個邊，首先把樹任意 rooted
- 給定 $\gamma$，做一次 traversal ，可以找到 $v$ 使得
- $e(T_v)\ge \gamma$
- $e(T_{child})< \gamma$ 對所有的 $child$
- 可以從 $v$ 和他的 child 中適當的挑出 $T_1$ 使得
- $\gamma\le e(T_1)< 2\gamma$
- 設定 $\gamma$ 成 $n/3$，則 $ratio\le 2$
- $n/3\le e(T_1)< 2n/3$
- $n/3< e(T_2)\le 2n/3$
- 大塊那塊最多只有 $2n/3$，小塊那塊至少也有 $n/3$
- **k-split 的 ratio 最多為 3 切法**
- 
- **Induction** 證明 ratio 最多為 3
- $i=1$ 時 $M_1/m_1=1$
- 假設 $i=k$ 時 $M_k/m_k\le 3$，則 $i=k+1$ 時
- $M_{k+1}\le M_k$
- $m_{k+1}=\min\{m_k,\frac{1}{3}M_k\}\ge\frac{1}{3}M_k$
- 因此 $M_{k+1}/m_{k+1}\le 3$
- 時間複雜度：
- 每個 iteration 執行時間為 $O(M_i)$
- $M_i\le3m_i\le3\frac{n-M_i}{i-1}$ $\rightarrow$ $M_i\le\frac{3n}{i+2}$
- 總共執行時間：
- $O(klogk)$：用 heap 來每次找最大塊
- $O(M_1+M_2+...+M_k)\\=3nO(\frac{1}{3}+\frac{1}{4}+...+\frac{1}{k+2})\\<3nO(\frac{1}{1}+\frac{1}{2}+...+\frac{1}{k})\\=3nO(logk)=O(nlogk)$