---
# System prepended metadata

title: 課程｜圖論演算法
tags: [課程]

---

# 圖論演算法

## 1.Counting # Spanning Tree
- 在 $K_n$ 中的 Spanning Tree 數量為 $n^{n-2}$，可以和 Prufer sequence 一一對應。
    - Tree to sequence
        - ![](https://i.imgur.com/zdVCrgU.png)
    - Sequence to Tree
        - ![](https://i.imgur.com/zLgmCRa.png)
- General Graph 中的 Spanning Tree 數量，滿足遞迴關係 $n(G)=n(G\setminus e)+n(G-e)$
## 2.Minumum Spanning Tree
- **Boruvka’s Algorithm** ： $O(mlogn)$
    - ![](https://i.imgur.com/x05cKBg.png)
- **Prim’s Algorithm** ： 
    - ![](https://i.imgur.com/FsOGBF0.png)
    - 找所有的邊最小的：$O(mn)$
    - Binary Heap：$O(mlogn)$
    - Fibonacci Heap：$O(m+nlogn)$
- **Kruskal’s Algorithm** ： 用disjoint set ，$O(mlogn)$
    - ![](https://i.imgur.com/6O66c1M.png)
- **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** ： 無負邊才可以使用
    - ![](https://i.imgur.com/qGFUspI.png)
    - 找所有的點最小的：$O(n^2)$
    - Binary Heap：$O(mlogn)$
    - Fibonacci Heap：$O(m+nlogn)$
- **Bellman-Ford Algorithm** ： relax $n-1$ 次，並檢測有無負環，$O(mn)$
    - ![](https://i.imgur.com/TmhrMqU.png)
- **Lawler Algorithm** ： 無環 → 照 topologic order → $O(m+n)$
## All pair shortest path：
- **Floyd-Warshall Algorithm** ： $O(n^3)$
    - ![](https://i.imgur.com/kjcwCNf.png)
    - 設 $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))$
        - ![](https://i.imgur.com/jTzneU9.png)
        - 給定 $\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)$
        - 證明：
            - ![](https://i.imgur.com/KwGumbX.png)
            - $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}$
        - ![](https://i.imgur.com/44WxiFJ.png)
            - $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)**
    - ![](https://i.imgur.com/mpyLz5n.png)
    - 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)\}$
        - ![](https://i.imgur.com/rrfbrcX.png)
    - 找一棵樹 $T$ 的 Diameter
        - ![](https://i.imgur.com/grepH9X.png)
    - 找一棵樹 $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**
    - ![](https://i.imgur.com/mB1HPGV.png)
    - 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\}$
        - ![](https://i.imgur.com/FRcpSXa.png)
        - ![](https://i.imgur.com/BIYs9va.png)
- **Approximation**
    - ![](https://i.imgur.com/jTL1DM9.png)
    - $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 切法**
    - ![](https://i.imgur.com/3YFy9kj.png)
    - **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)$


