連通且無環的無向圖：樹

在圖論中，我們將連通、無環的無向圖稱為樹。本文簡介樹的性質。

1　準備工作

1.1　基本術語

設 $G$ 為一無向圖。設 $V(G)$ 與 $E(G)$ 分別為 $G$ 中的頂點（vertex）與邊（edge）所構成的集合。我們以 $\{u, v\}$ 表示連接 $u$ 與 $v$ 的邊。

對於 $u \in V(G)$，我們定義集合 \[N_G(u) = \bigl\{v \in V(G): \{u, v\} \in E(G)\bigr\} \period\] $N_G(u)$ 中的頂點稱為 $u$ 在 $G$ 中的鄰居（neigh­bor）。

若 $G$ 不包含環，則稱 $G$ 無環（acyclic）。若 $\lvert V(G) \rvert \geq 1$ 且 $G$ 中任兩頂點間皆存在一路徑，則稱 $G$ 連通（connected）。

1.2　樹

無環的無向圖稱為森林（forest）；連通的森林稱為樹（tree）。

1.3　準備工作

定理 1、2 主要用於證明定理 3。

定理 1　下列敘述對任意滿足 $\lvert V(T) \rvert \geq 2$ 的有限樹 $T$ 皆成立。

證明　首先證明 (a)。設 $P$ 是 $T$ 中最長的一條路徑（即含有的邊數最多），此時 $\lvert V(P) \rvert \geq 2 \period$我們說明對 $P$ 的任一端點 $u \comma$皆有 $\lvert N_T(u) \rvert = 1 \period$設 $v \in N_T(u) \setminus N_P(u) \period$

狀況 1：$v \in V(P) \period$設 $Q$ 為 $P$ 中連接 $u$ 與 $v$ 的路徑，此時 $Q$ 加上邊 $\{u, v\}$ 後會形成環，矛盾。

狀況 2：$v \notin V(P) \period$此時 $P$ 加上邊 $\{u, v\}$ 後會形成比 $P$ 更長的路徑，矛盾。

由此可知 $N_T(u) \setminus N_P(u) = \varnothing$，即 $N_T(u) = N_P(u) \comma$故 $\lvert N_T(u) \rvert = 1 \period$

接著證明 (b)。由於 $T$ 無環，故 $T - \{u\}$ 亦無環。對於任意 $v, w \in V(T) \setminus \{u\}$，由於 $T$ 連通，我們能找到一條 $T$ 中連接 $v$ 與 $w$ 的路徑 $P \textrm{；}$由於 $\lvert N_P(u) \rvert \leq \lvert N_T(u) \rvert = 1$ 且 $u \notin \{v, w\}$，我們有 $u \notin V(P)$，即 $P \subseteq T - \{u\}$。故 $T - \{u\}$ 連通。至此定理得$\textrm{證。}\mkern6mu\blacksquare$

定理 2　設 $G$ 為一連通的無向圖，其中有一環 $C$。則對任意 $e \in E(C)$，$G \setminus \{e\}$ 連通。

證明　設 $u, v \in V(G)$ 相異，並設 $P$ 為 $G$ 中連接 $u$ 與 $v$ 的路徑。我們證明在 $G \setminus \{e\}$ 中也能找到一條連接 $u$ 與 $v$ 的路徑。

狀況 1：$e \notin E(P)$。此時 $P$ 即為 $G \setminus \{e\}$ 中的 $(u,v)$ 路徑。

狀況 2：$e \in E(P)$。設 $e = \{x, y\}$，其中在 $P$ 當中 $x$ 位於 $u$ 與 $y$ 之間。設 $P_1$ 為 $P$ 當中連接 $u$ 與 $x$ 的路徑，設 $P_2 = C \setminus \{e\}$，設 $P_3$ 為 $P$ 當中連接 $y$ 與 $v$ 的路徑；設 $H = P_0 \cup P_1 \cup P_2$。此時 $H$ 連通，$\{u, v\} \subseteq V(H)$ 且 $e \notin E(H)$，故 $H$ 中連接 $u$ 與 $v$ 的路徑即為 $G \setminus \{e\}$ 中的一條連接 $u$ 與 $v$ 的路徑。至此定理得$\textrm{證。}\mkern6mu\blacksquare$

2　樹的等價條件

2.1　邊數等於頂點數減 1

定理 3 說明我們可利用頂點數與邊數的差判斷連通的無向圖是否為樹。

定理 3　下列敘述對任意有限的無向圖 $G$ 皆成立。

證明　首先證明 (a)。我們對 $\lvert V(G) \rvert$ 使用數學歸納法。當 $\lvert V(G) \rvert = 1$ 時，有 $\lvert E(G) \rvert = 0 = \lvert V(G) \rvert - 1 \period$接著我們假設 (a) 在 $\lvert V(G) \rvert = n$ 時成立，其中 $n \geq 1 \comma$並說明 (a) 在 $\lvert V(G) \rvert = n+1$ 時也成立：由定理 1 知存在 $u \in V(G)$ 使得 $\lvert N_G(u) \rvert = 1$，且 $G - \{u\}$ 是樹。設 $G' = G - \{u\} \comma$由 $\lvert V(G') \rvert = n$ 可得 \[\begin{split}\lvert E(G) \rvert - 1 &= \lvert E(G') \rvert \\ &= \lvert V(G') \rvert - 1 \\ &= n-1 \comma\end{split}\] 故 $\lvert E(G) \rvert = n = \lvert V(G) \rvert - 1 \period$

接著證明 (b)。設 $G$ 的所有連通分量為 $U_0, U_1, \ldots, U_{k-1} \period$可知對每個 $i \in \{0, 1, \ldots, k \varminus 1\} \comma$$G[U_i]$ 皆為樹。此時套用 (a)，我們有 \[ \begin{split} \lvert V(G) \rvert - 1 &= \lvert E(G) \rvert \\ &= \sum_{i=0}^k \lvert E(G[U_i]) \rvert \\ &= \sum_{i=0}^k (\lvert U_i \mkern-1mu \rvert - 1) \\ &=\rule[-1.8ex]{0pt}{4.8ex} \lvert V(G) \rvert - k \period \end{split} \] 故 $k = 1$，即 $G$ 連通，故 $G$ 是樹。

最後證明 (c)。由定理 2 可知若 $G$ 含有環，則存在 $e \in E(G)$ 使得 $G \setminus \{e\}$ 連通。故我們能找到 $F \subseteq E(G)$ 使得 $G \setminus F$ 連通且無環，即 $G \setminus F$ 是樹。套用 (a)，我們有 \[ \lvert E(G \setminus F) \rvert = \lvert V(G) \rvert - 1 = \lvert E(G) \rvert \comma \] 即 $G \setminus F = G$，故 $G$ 是樹。至此定理得$\textrm{證。}\mkern6mu\blacksquare$

2.2　路徑唯一

定理 4 說明樹中任兩頂點間均存在唯一路徑。

定理 4　對任意有限的無向圖 $G$，$G$ 是樹若且唯若 $G$ 中任意兩頂點間均存在唯一一條路徑。

證明　我們首先證明若 $G$ 是樹，則 $G$ 的任意兩頂點之間存在唯一一條路徑。由 $G$ 連通可知任兩頂點間至少有一條路徑。假設 $G$ 中有兩相異路徑 $P_0$ 與 $P_1$ 其端點相同，且 $\lvert E(P_0) \rvert + \lvert E(P_1) \rvert$ 為最小。設 $u$ 與 $v$ 為 $P_0 \jcomma P_1$ 的端點。若 $P_0$ 與 $P_1$ 相交於端點 $u \jcomma v$ 以外的頂點 $w \comma$並設 $Q_i$ 為 $P_i$ 中連接 $u$ 與 $w$ 的路徑，其中 $i \in \{0,1\} \comma$則我們有 \[\begin{split}\lvert E(Q_0) \rvert + \lvert E(Q_1) \rvert < \lvert E(P_0) \rvert + \lvert E(P_1) \rvert \comma\end{split}\] 導致矛盾。故 $P_0$ 與 $P_1$ 只相交於 $u \jcomma v$ 兩頂點，亦即 $P_0 \cup P_1$ 為一環，矛盾。因此任兩條相異路徑必定具有至少一個相異的端點，即任意兩頂點間的路徑唯一。

接著證明若 $G$ 的任意兩頂點之間存在唯一一條路徑，則 $G$ 是樹。由任兩頂點間均存在路徑可知 $G$ 連通。若 $G$ 中有一環 $C$，則任取相異 $u, v \in V(C)$ 時，$C$ 中會有兩條連接 $u$ 與 $v$ 的路徑，這兩條路徑也在 $G$ 中，導致矛盾，故 $G$ 無環。至此定理得$\textrm{證。}\mkern6mu\blacksquare$

參考資料

1. Douglas B. West. Introduction to graph theory. Prentice-Hall, second edition, 2001.