直線平面嵌入
本文簡述平面嵌入（planar embedding）的性質，並介紹平版圖的歐拉公式（Euler’s formula）。
1 基本術語
1.1 線段
對任意 $p, q \in \RR^2 \comma$我們以 \[\begin{split} [p, q] = \bigl\{(1-t)p + tq: 0 \leq t \leq 1\bigr\} \period \end{split}\] 代表連接 $p$ 與 $q$ 的線段。
給定一無向圖 $G \comma$若 $\beta \colon V(G) \to \RR^2$ 為一映射且 $\{u, v\} \in E(G) \comma$則我們定義 \[\begin{split}\beta[\{u, v\}] = [\beta(u), \beta(v)] \period\end{split}\]
1.2 直線平面嵌入
設 $G$ 為一無向圖。給定一映射 $\beta \colon V(G) \to \RR^2$，若以下條件皆成立，則我們稱 $\beta$ 為 $G$ 的一個直線平面嵌入（straight-line planar embedding）：
- 對任意相異 $u, v \in V(G) \comma$均有 $\beta(u) \neq \beta(v) \period$
- 對任意相異 $\{u, v\} \cm \{u', v'\} \in E(G) \comma$均有 \[\begin{split}\beta[\{u, v\}] \cap \beta[\{u', v'\}] \subseteq \bigl\{\beta(u), \beta(v)\bigr\} \cap \bigl\{\beta(u'), \beta(v')\bigr\} \period\end{split}\]
若無向圖 $G$ 存在一直線平面嵌入，則我們稱 $G$ 為平面圖（planar graph）。
若 $G$ 為一無向圖且 $\beta \colon V(G) \to \RR^2$ 為 $G$ 的直線平面嵌入，則我們稱 $(G, \beta)$ 為一直線平版圖（straight-line plane graph）。
範例 1 設無向圖 $G$ 為具有 4 個頂點的完全圖，其中 $V(G) = \{v_0, v_1, v_2, v_3\} \period$
- 若映射 $\beta \colon V(G) \to \RR^2$ 滿足 \[\begin{split} \beta(v_0) = \begin{pmatrix}0 \\ 0\end{pmatrix} \comma \quad &\beta(v_1) = \begin{pmatrix}3 \\ 0\end{pmatrix} \comma \\[2ex] \beta(v_2) = \begin{pmatrix}0 \\ 3\end{pmatrix} \comma \quad &\beta(v_3) = \begin{pmatrix}1 \\ 1\end{pmatrix} \comma \end{split}\] 則 $\beta$ 是 $G$ 的直線平面嵌入。
- 若映射 $\beta' \colon V(G) \to \RR^2$ 滿足 \[\begin{split} \beta'(v_0) = \begin{pmatrix}0 \\ 0\end{pmatrix} \comma \quad &\beta'(v_1) = \begin{pmatrix}2 \\ 0\end{pmatrix} \comma \\[2ex] \beta'(v_2) = \begin{pmatrix}0 \\ 2\end{pmatrix} \comma \quad &\beta'(v_3) = \begin{pmatrix}2 \\ 2\end{pmatrix} \comma \end{split}\] 則由於 \[\begin{split}\rod{4}{0}\frac{\beta'(v_0) + \beta'(v_3)}{2} = \begin{pmatrix}1 \\ 1\end{pmatrix} = \frac{\beta'(v_1) + \beta'(v_2)}{2} \comma\end{split}\]可知 $\beta'$ 不是 $G$ 的直線平面嵌入。
由於 $\beta$ 是 $G$ 的直線平面嵌入，故 $G$ 為平面圖，且 $(G, \beta)$ 為一直線平版圖。
1.3 面
對任意 $G$ 的直線平面嵌入 $\beta \comma$我們定義 \[\begin{split}\beta[G] = \bigcup_{v \in V(G)} \bigl\{\beta(v)\bigr\} \cup \bigcup_{e \in E(G)} \beta[e] \period\end{split}\] 我們將 $\RR^2 \setminus \beta[G]$ 中的區域稱為直線平版圖 $(G, \beta)$ 的面（face）。
2 歐拉公式
以下我們介紹歐拉公式（Euler’s formula）：給定頂點數、邊數，我們就能知道一個（直線）平版圖所具有的面數。
2.1 樹
定理 1 說明有限樹構成的直線平版圖必定只具有 1 個面。
定理 1 設 $M = (G, \beta)$ 為一直線平版圖，其中 $G$ 為有限樹，則 $M$ 恰有 1 個面。
證明 對 $\lvert V(G) \rvert$ 採用數學歸納法。當 $\lvert V(G) \rvert \in \{1, 2\}$ 時，由於 $\beta[G]$ 恰含有一個點或一線段，故可驗證 $\RR^2 \setminus \beta[G]$ 連通。
接著假設定理在 $\lvert V(G) \rvert = k \geq 2$ 時成立，我們說明定理對滿足 $\lvert V(G) \rvert = k + 1$ 的樹 $G$ 亦成立。由於 $G$ 是樹且 $\lvert V(G) \rvert \geq 2 \comma$我們能找到一個 $u_0 \in V(G)$ 使得 $\lvert N_G(u_0) \rvert = 1 \period$此時 $H = G - \{u_0\}$ 是樹。設 $v \in N_G(u_0) \period$
我們將 $N_G(v)$ 中的頂點依照嵌入 $\beta$ 圍繞 $v$ 逆時針排序：設逆時針排序後 $N_G(v)$ 中的頂點依序為 $u_0, u_1, \ldots, u_{d-1} \comma$即我們有 \[\begin{split}0 < \alpha_1 < \alpha_2 < \cdots < \alpha_{d-1} < 2\pi \comma\end{split}\] 其中 $\alpha_i \in (0, 2\pi)$ 對任意 $i \in \{1 \cm 2, \ldots \cm d \varminus 1\}$ 均滿足 \[\begin{split}\rod{4}{0}\begin{pmatrix*}[r]\cos\alpha_i & -\sin\alpha_i \\ \sin\alpha_i & \cos\alpha_i\end{pmatrix*}\frac{\beta(u_0) - \beta(v)}{\lVert \beta(u_0) - \beta(v) \rVert} = \frac{\beta(u_i) - \beta(v)}{\lVert \beta(u_i) - \beta(v) \rVert} \period\end{split}\]
對任意 $\{x, y\} \in E(G)$ 與 $z \in V(G) \setminus \{x, y\} \comma$我們定義 \[\begin{split}d_\beta(z, \{x, y\}) = \min\,\bigl\{\lVert \beta(z) - p \rVert: p \in [\beta(x), \beta(y)]\bigr\} \period\end{split}\] 設 $\delta(M)$ 為所有 $d_\beta(z, \{x, y\})$ 中的最小值，其中 $\{x, y\} \in E(G)$ 且 $z \in V(G) \setminus \{x, y\} \period$設 \[\begin{split} \sigma = \min\biggl\{\sin\frac{\alpha_1}{2}, \sin\frac{\alpha_{d-1}}{2}, \frac{\sqrt{2}}{2} \biggr\} \period \end{split}\] 對任意 $0 < \epsilon < \delta(C)/(2\sigma) \comma$我們定義折線段 $P(\epsilon)$ 如下：
- 設 \[\begin{split} t &= \frac{1}{\tan(\alpha_1/2)} \comma \\ t' &= \frac{1}{\tan(\alpha_{d-1}/2)} \comma \\[2ex] r &= \frac{\beta(u_0) - \beta(v)}{\lVert \beta(u_0) - \beta(v) \rVert} \period \end{split}\]
- 設 \[\begin{split} p &= \beta(v) + \epsilon\begin{pmatrix*}[r]t & -1 \\ 1 & t\end{pmatrix*}r \comma \\ p' &= \beta(v) + \epsilon\begin{pmatrix*}[r]t' & 1 \\ -1 & t'\end{pmatrix*}r \comma \\ q &= \beta(u_0) + \epsilon\begin{pmatrix*}[r]1 & -1 \\ 1 & 1\end{pmatrix*}r \comma \\ q' &= \beta(u_0) + \epsilon\begin{pmatrix*}[r]1 & 1 \\ -1 & 1\end{pmatrix*}r \comma \end{split}\] 並設 $P(\epsilon)$ 為 $(p, q, q', p')$ 所構成的折線段。
對任意 $0 < \epsilon < \delta(C)/(2\sigma) \comma$折線段 $P(\epsilon)$ 均不與 $\beta[G]$ 相交。因此，若一折線段 $Q \subseteq \RR^2 \setminus \beta[H]$ 與 $\beta[\{u, v_0\}]$ 相交，則可找到一折線段 $P(\epsilon)$ 使得 $Q \cup P(\epsilon)$ 中含有連接 $Q$ 的兩端點且不與 $\beta[G]$ 相交的折線段 $Q' \comma$其中 $0 < \epsilon < \delta(C)/(2\sigma) \period$
由歸納假設知 $\RR^2 \setminus \beta[H]$ 連通。故 $\RR^2 \setminus \beta[G]$ 連通，定理得$\textrm{證。}\mkern6mu\blacksquare$
2.2 連通圖
環在直線嵌入之下會形成一多邊形，由喬登多邊形定理（可參見〈喬登多邊形定理〉）可知多邊形會將歐氏平面分為 2 個區域，因此具有環的直線平版圖至少有 2 個面。
喬登多邊形定理 若 $C$ 為一多邊形，則 $\RR^2 \setminus C$ 恰具有 2 個區域。
利用喬登多邊形定理，我們可以證明適用於任意連通平版圖的歐拉公式。
定理 2（連通平版圖的歐拉公式） 設 $M = (G, \beta)$ 為一直線平版圖，其中 $G$ 有限且連通。則 $M$ 恰有 $\lvert E(G) \rvert - \lvert V(G) \rvert + 2$ 個面。
證明 對 $\lvert E(G) \rvert - \lvert V(G) \rvert$ 採用數學歸納法。由於 $G$ 連通，故 $\lvert E(G) \rvert - \lvert V(G) \rvert \geq -1 \period$
當 $\lvert E(G) \rvert - \lvert V(G) \rvert = -1$ 時，$G$ 是樹，故由定理 1 知 $M$ 具有 \[\begin{split}1 = (-1) + 2 = \lvert E(G) \rvert - \lvert V(G) \rvert + 2\end{split}\] 個面。
接著假設定理在 $\lvert E(G) \rvert - \lvert V(G) \rvert = k \geq -1$ 時成立，我們說明定理在 $\lvert E(G) \rvert - \lvert V(G) \rvert = k+1$ 時也成立。由於 $\lvert E(G) \rvert > \lvert V(G) \rvert - 1 \comma$故 $G$ 具有一環 $C \period$設 $e = \{x, y\} \in E(C) \comma$並設 $H = G \setminus \{e\} \period$由於 $\beta[e] \subseteq \beta[C] \comma$由喬登多邊形定理可知 $\beta[e]$ 的兩側在 $\RR^2 \setminus \beta[G]$ 中分屬不同的區域 $D \jcomma D' \period$由於在 $\RR^2 \setminus \beta[H]$ 中 $D$ 中的點均與 $D'$ 中的點連通，故 $M = (G, \beta)$ 的面數比 $(H, \beta)$ 多 1。由此可知，$M$ 具有 \[\begin{split} (\lvert E(H) \rvert - \lvert V(H) \rvert + 2) + 1 = \lvert E(G) \rvert - \lvert V(G) \rvert + 2 \end{split}\] 個面。定理得$\textrm{證。}\mkern6mu\blacksquare$
參考資料
- Reinhard Diestel. Graph theory. Springer, third edition, 2005.