圖論-L2

L2 樹與距離

符號定義

符號	意義
$d_G(u,v)$	$u$ 與 $v$ 間的最短路徑長度（距離）
$\varepsilon_G(v)$	頂點 $v$ 的離心率
$\operatorname{diam}(G)$	圖 $G$ 的直徑 (diameter)
$\operatorname{rad}(G)$	圖 $G$ 的半徑 (radius)
$G[S]$	頂點集合 $S$ 的導出子圖
$K_n$、$P_n$、$C_n$	完全圖、$n$ 點路徑圖、$n$ 點環圖
$K_{m,n}$；$K_{1,n}$	完全二部圖；星圖
$h$；$L$；$I$	樹高；葉節點數；內部節點數
$w(e)$；$w(T)$	邊權重；生成樹的邊權重總和

樹與森林

名詞	定義/性質
Tree	連通 (connected) 且無環 (acyclic) 的圖。
Forest	每一個連通分支 (component) 都是樹；等價於無環圖。
Leaf	在至少有兩個頂點的普通樹中，度數為 $1$ 的頂點。
Internal vertex	普通樹中不是葉節點的頂點 (根樹中的葉、內部點另依子節點數判斷)。
Cut-edge / Bridge (割邊)	移除後增加連通分支數的邊。樹的每一條邊都是割邊。
Cut-vertex (割點)	移除頂點及其關聯邊後，增加連通分支數的頂點。樹的葉節點不是割點。

• 特例：$K_1$、$K_2$、$P_n$、星圖 $K_{1,n}$ 都是樹。
• 森林若有 $n$ 個頂點與 $c$ 個連通分支，則 $m=n-c$ (邊數)。

樹的基本性質

• 樹的邊數: 若 $T$ 有 $n$ 個頂點，${|E(T)|=n-1}$ (講義 P13)
• 當 $n\ge2$ 時，樹至少有兩個度數為 $1$ 的頂點。 (講義 P16-17)
• 對樹中任兩個不同頂點 $u,v$，恰好存在唯一一條 $u-v$ 路徑。連通保證存在。 (講義 P19-20)
  • 若有兩條不同簡單路徑，會形成環，矛盾。
• 對 $n\ge3$ 的樹，割邊恰有 $n-1$ 條；至少兩個葉子不是割點，因此割點至多 $n-2$ 個。

---

對 $n$ 個頂點的圖 $T$，以下敘述等價：

• $T$ 是樹（連通且無環）。
• $T$ 連通且 $|E(T)|=n-1$。
• $T$ 無環且 $|E(T)|=n-1$。
• $T$ 連通且每一條邊都是割邊。
• 任意兩個不同頂點間有唯一一條路徑。
• $T$ 無環，且在任意兩個原本不相鄰的頂點間加上一條邊，會形成唯一一個環。

只有 $m=n-1$，不能判定是樹；還需確認連通或無環。
證明在講義 P28-31

距離、離心率、直徑與半徑

名詞	定義/公式
Distance (距離)	$\displaystyle d_G(u,v)=\min\{ u-v~\text{路徑的長度}\}$ ；若無路徑則為 $\infty$。
Eccentricity (離心率)	$\displaystyle \varepsilon_G(u)=\max_{v\in V(G)}d_G(u,v)$，即從 $u$ 出發到最遠頂點的距離。
Diameter (直徑)	$\displaystyle \operatorname{diam}(G)=\max_{u,v\in V(G)}d_G(u,v)=\max_{u}\varepsilon_G(u)$。
Radius (半徑)	$\displaystyle \operatorname{rad}(G)=\min_{u\in V(G)}\varepsilon_G(u)$。
Center (中心)	離心率等於半徑的所有頂點形成的頂點導出子圖；中心可能不只一個頂點。

---

圖	$\operatorname{diam}$	$\operatorname{rad}$	中心
$K_n\ (n\ge2)$	$1$	$1$	全部頂點 ($K_n$)
$C_n\ (n\ge3)$	$\lfloor n/2\rfloor$	$\lfloor n/2\rfloor$	全部頂點（$C_n$）
$P_n\ (n\ge2)$	$n-1$	$\lfloor n/2\rfloor$	中間一點 ($n$ 奇) 或中間相鄰兩點 ($n$ 偶)
$K_{m,n}\ (m,n\ge2)$	$2$	$2$	全部頂點
$K_{1,m}\ (m\ge2)$	$2$	$1$	星圖中央頂點
Petersen graph	$2$	$2$	全部頂點

---

• 若 $H$ 是 $G$ 的生成子圖 (保留全部頂點、可刪邊): ${d_H(u,v)\ge d_G(u,v)}\quad\Longrightarrow\quad{\operatorname{diam}(H)\ge\operatorname{diam}(G)}$ (講義 P39-40)

• 若 $H$ 只是普通子圖，頂點也可能刪除，以上 不一定成立。

• 對簡單圖 $G$，${\operatorname{diam}(G)\ge3\implies\operatorname{diam}(\overline G)\le3}$ (講義 P43-47)

• 樹的中心恰為一個頂點，或一對相鄰的頂點。

  • 找樹中心的方式: 反覆同時移除所有葉節點，直到只剩一個頂點或相鄰兩點。此過程保留中心。

生成樹與計數

生成樹 Spanning tree：$G$ 的一個子圖 $T$，同時滿足 $V(T)=V(G)$ 且 $T$ 為樹。連通圖至少有一棵生成樹；可以不斷刪去環上的邊得到。

• 每棵生成樹都恰好有 $n-1$ 條邊。
• 若 $G$ 有 $m$ 條邊，則其生成子圖總數為 $2^m$。
• 在固定 $n$ 個有標號頂點上，簡單圖總數為: ${2^{\binom n2}=2^{n(n-1)/2}}$

Cayley 定理: 對 $n\ge2$，$K_n$ 的生成樹數量 (頂點有標號，不以同構合併) 是 ${n^{n-2}}$

最小生成樹 MST

Kruskal	Prim
全圖按邊權排序，合併不同連通分支	從一個起點逐步擴張已選頂點集合
核心檢查：是否形成環	核心檢查：是否跨越已選與未選頂點
形成森林後逐漸合併成一棵樹	從一個頂點逐漸長成一棵樹

• Kruskal: ${O(|E|\log |E|)=O(|E|\log |V|)}$

有根樹 Rooted tree

選樹 $T$ 的一個頂點 $r$ 作根，記為 $(T,r)$。不同的根會產生不同的有根樹結構。

名詞	定義
Root	指定為起點的頂點，沒有父節點。
Parent	對非根節點 $u$，根到 $u$ 的唯一簡單路徑中緊鄰 $u$ 的前一個頂點。
Child	某節點相鄰的頂點中，除父節點外，沿樹向下的頂點。
Sibling	具有相同父節點的兩個節點。
Ancestor	根到 $u$ 的路徑上除 $u$ 外的所有節點。
Descendant	若根到 $u$ 的路徑包含 $x$，則 $u$ 是 $x$ 的子孫。
Leaf	在有根樹中，沒有任何子節點的節點。
Internal vertex	在有根樹中，至少有一個子節點的節點；根即使只有一個子節點，仍是內部點。

• 普通無根樹常以 $\deg(u)=1$ 定義葉；有根樹則以子節點數 $=0$ 判斷葉。
• 根只有一條相鄰邊時，度數雖為 1，卻不是有根樹的葉節點。

二元樹 Binary tree

二元樹: 每個節點最多兩個子節點，且分左子節點／右子節點；左右位置有區別，不可任意互換。

左子樹／右子樹: 以某節點的左／右子節點為根向下形成的子樹。

---

• 節點深度 Depth: 根到該節點的路徑長度；根深度為 $0$。
• 節點高度 Height: 該節點往下走到子孫葉節點的最長路徑長度；葉節點高度為 $0$。
• 整棵樹高度 $h$: 根節點的高度；深度 $i$ 那層最多有 $2^i$ 個節點。

高度為 $h$ 的一般二元樹，總頂點數 $n$ 的界限: ${h+1\le n\le 2^{h+1}-1}$

反推樹高的下界: ${h\ge\lceil\log_2(n+1)\rceil-1}$

有 $k$ 個內部點的二元樹，節點總數最多為 $2k+1$。

---

類型	判準	特別性質
Full binary tree	每個節點的子節點數恰好是 0 或 2。	若有 $k$ 個內部點：總節點 $2k+1$，葉節點 $k+1$。
Complete binary tree	除最後一層外每層全滿，最後一層由左至右填入。	$2^h\le n\le 2^{h+1}-1$。
Perfect binary tree	每一層全部填滿。	$n=2^{h+1}-1$；同時是 Full 與 Complete。

Full binary tree: ${2h+1\le n\le2^{h+1}-1}$

Complete binary tree: ${h=\lfloor\log_2 n\rfloor=\lceil\log_2(n+1)\rceil-1}$

平衡樹 Balanced tree

• 葉節點所在層數相差至多 1