直線平面嵌入

本文簡述平面嵌入（pla­nar em­bed­ding）的性質，並介紹平版圖的歐拉公式（Euler’s for­mu­la）。

1　基本術語

1.1　線段

對任意 $p,q\in {\mathbb{R}}^2\text{，}$我們以 $$\begin{array}{r}[p,q]=\{(1-t)p+tq:0\le t\le 1\}\text{。}\end{array}$$ 代表連接 $p$ 與 $q$ 的線段。

給定一無向圖 $G\text{，}$若 $\beta :V(G)\to {\mathbb{R}}^2$ 為一映射且 $\{u,v\}\in E(G)\text{，}$則我們定義 $$\begin{array}{r}\beta [\{u,v\}]=[\beta (u),\beta (v)]\text{。}\end{array}$$

1.2　直線平面嵌入

設 $G$ 為一無向圖。給定一映射 $\beta :V(G)\to {\mathbb{R}}^2$，若以下條件皆成立，則我們稱 $\beta$ 為 $G$ 的一個直線平面嵌入（straight-line pla­nar em­bed­ding）：

1. 對任意相異 $u,v\in V(G)\text{，}$均有 $\beta (u)\ne \beta (v)\text{。}$
2. 對任意相異 $\{u,v\},\{u^{\prime },v^{\prime }\}\in E(G)\text{，}$均有 $$\begin{array}{r}\beta [\{u,v\}]\cap \beta [\{u^{\prime },v^{\prime }\}]\subseteq \{\beta (u),\beta (v)\}\cap \{\beta (u^{\prime }),\beta (v^{\prime })\}\text{。}\end{array}$$

若無向圖 $G$ 存在一直線平面嵌入，則我們稱 $G$ 為平面圖（planar graph）。

若 $G$ 為一無向圖且 $\beta :V(G)\to {\mathbb{R}}^2$ 為 $G$ 的直線平面嵌入，則我們稱 $(G,\beta )$ 為一直線平版圖（straight-line plane graph）。

範例 1　設無向圖 $G$ 為具有 4 個頂點的完全圖，其中 $V(G)=\{v_0,v_1,v_2,v_3\}\text{。}$

1. 若映射 $\beta :V(G)\to {\mathbb{R}}^2$ 滿足 $$\begin{array}{rl}\beta (v_0)=\left(\begin{array}{c}0\\ 0\end{array}\right)\text{，}& \beta (v_1)=\left(\begin{array}{c}3\\ 0\end{array}\right)\text{，}\\ \beta (v_2)=\left(\begin{array}{c}0\\ 3\end{array}\right)\text{，}& \beta (v_3)=\left(\begin{array}{c}1\\ 1\end{array}\right)\text{，}\end{array}$$ 則 $\beta$ 是 $G$ 的直線平面嵌入。
2. 若映射 ${\beta }^{\prime }:V(G)\to {\mathbb{R}}^2$ 滿足 $$\begin{array}{rl}{\beta }^{\prime }(v_0)=\left(\begin{array}{c}0\\ 0\end{array}\right)\text{，}& {\beta }^{\prime }(v_1)=\left(\begin{array}{c}2\\ 0\end{array}\right)\text{，}\\ {\beta }^{\prime }(v_2)=\left(\begin{array}{c}0\\ 2\end{array}\right)\text{，}& {\beta }^{\prime }(v_3)=\left(\begin{array}{c}2\\ 2\end{array}\right)\text{，}\end{array}$$ 則由於 $$\begin{array}{r}\frac{{\beta }^{\prime }(v_0)+{\beta }^{\prime }(v_3)}{2}=\left(\begin{array}{c}1\\ 1\end{array}\right)=\frac{{\beta }^{\prime }(v_1)+{\beta }^{\prime }(v_2)}{2}\text{，}\end{array}$$可知 ${\beta }^{\prime }$ 不是 $G$ 的直線平面嵌入。

由於 $\beta$ 是 $G$ 的直線平面嵌入，故 $G$ 為平面圖，且 $(G,\beta )$ 為一直線平版圖。

1.3　面

對任意 $G$ 的直線平面嵌入 $\beta \text{，}$我們定義 $$\begin{array}{r}\beta [G]=\bigcup _{v\in V(G)}\{\beta (v)\}\cup \bigcup _{e\in E(G)}\beta [e]\text{。}\end{array}$$ 我們將 ${\mathbb{R}}^2\setminus \beta [G]$ 中的區域稱為直線平版圖 $(G,\beta )$ 的面（face）。

2　歐拉公式

以下我們介紹歐拉公式（Euler’s for­mu­la）：給定頂點數、邊數，我們就能知道一個（直線）平版圖所具有的面數。

2.1　樹

定理 1 說明有限樹構成的直線平版圖必定只具有 1 個面。

定理 1　設 $M=(G,\beta )$ 為一直線平版圖，其中 $G$ 為有限樹，則 $M$ 恰有 1 個面。

證明　對 $|V(G)|$ 採用數學歸納法。當 $|V(G)|\in \{1,2\}$ 時，由於 $\beta [G]$ 恰含有一個點或一線段，故可驗證 ${\mathbb{R}}^2\setminus \beta [G]$ 連通。

接著假設定理在 $|V(G)|=k\ge 2$ 時成立，我們說明定理對滿足 $|V(G)|=k+1$ 的樹 $G$ 亦成立。由於 $G$ 是樹且 $|V(G)|\ge 2\text{，}$我們能找到一個 $u_0\in V(G)$ 使得 $|N_G(u_0)|=1\text{。}$此時 $H=G-\{u_0\}$ 是樹。設 $v\in N_G(u_0)\text{。}$

我們將 $N_G(v)$ 中的頂點依照嵌入 $\beta$ 圍繞 $v$ 逆時針排序：設逆時針排序後 $N_G(v)$ 中的頂點依序為 $u_0,u_1,\dots ,u_{d-1}\text{，}$即我們有 $$\begin{array}{r}0<{\alpha }_1<{\alpha }_2<\cdots <{\alpha }_{d-1}<2\pi \text{，}\end{array}$$ 其中 ${\alpha }_i\in (0,2\pi )$ 對任意 $i\in \{1,2,\dots ,d-1\}$ 均滿足 $$\begin{array}{r}\left(\begin{array}{rr}\cos {\alpha }_i& -\sin {\alpha }_i\\ \sin {\alpha }_i& \cos {\alpha }_i\end{array}\right)\frac{\beta (u_0)-\beta (v)}{\Vert \beta (u_0)-\beta (v)\Vert }=\frac{\beta (u_i)-\beta (v)}{\Vert \beta (u_i)-\beta (v)\Vert }\text{。}\end{array}$$

對任意 $\{x,y\}\in E(G)$ 與 $z\in V(G)\setminus \{x,y\}\text{，}$我們定義 $$\begin{array}{r}{d}_{\beta }(z,\{x,y\})=\min \{\Vert \beta (z)-p\Vert :p\in [\beta (x),\beta (y)]\}\text{。}\end{array}$$ 設 $\delta (M)$ 為所有 $d_{\beta }(z,\{x,y\})$ 中的最小值，其中 $\{x,y\}\in E(G)$ 且 $z\in V(G)\setminus \{x,y\}\text{。}$設 $$\begin{array}{r}\sigma =\min \{\sin \frac{{\alpha }_1}{2},\sin \frac{{\alpha }_{d-1}}{2},\frac{\sqrt{2}}{2}\}\text{。}\end{array}$$ 對任意 $0<ϵ<\delta (C)/(2\sigma )\text{，}$我們定義折線段 $P(ϵ)$ 如下：

1. 設 $$\begin{array}{rl}t& =\frac{1}{\tan ({\alpha }_1/2)}\text{，}\\ t^{\prime }& =\frac{1}{\tan ({\alpha }_{d-1}/2)}\text{，}\\ r& =\frac{\beta (u_0)-\beta (v)}{\Vert \beta (u_0)-\beta (v)\Vert }\text{。}\end{array}$$
2. 設 $$\begin{array}{rl}p& =\beta (v)+ϵ\left(\begin{array}{rr}t& -1\\ 1& t\end{array}\right)r\text{，}\\ p^{\prime }& =\beta (v)+ϵ\left(\begin{array}{rr}{t}^{\prime }& 1\\ -1& t^{\prime }\end{array}\right)r\text{，}\\ q& =\beta (u_0)+ϵ\left(\begin{array}{rr}1& -1\\ 1& 1\end{array}\right)r\text{，}\\ q^{\prime }& =\beta (u_0)+ϵ\left(\begin{array}{rr}1& 1\\ -1& 1\end{array}\right)r\text{，}\end{array}$$ 並設 $P(ϵ)$ 為 $(p,q,q^{\prime },p^{\prime })$ 所構成的折線段。

對任意 $0<ϵ<\delta (C)/(2\sigma )\text{，}$折線段 $P(ϵ)$ 均不與 $\beta [G]$ 相交。因此，若一折線段 $Q\subseteq {\mathbb{R}}^2\setminus \beta [H]$ 與 $\beta [\{u,v_0\}]$ 相交，則可找到一折線段 $P(ϵ)$ 使得 $Q\cup P(ϵ)$ 中含有連接 $Q$ 的兩端點且不與 $\beta [G]$ 相交的折線段 $Q^{\prime }\text{，}$其中 $0<ϵ<\delta (C)/(2\sigma )\text{。}$

由歸納假設知 ${\mathbb{R}}^2\setminus \beta [H]$ 連通。故 ${\mathbb{R}}^2\setminus \beta [G]$ 連通，定理得證。

2.2　連通圖

環在直線嵌入之下會形成一多邊形，由喬登多邊形定理（可參見〈喬登多邊形定理〉）可知多邊形會將歐氏平面分為 2 個區域，因此具有環的直線平版圖至少有 2 個面。

喬登多邊形定理　若 $C$ 為一多邊形，則 ${\mathbb{R}}^2\setminus C$ 恰具有 2 個區域。

利用喬登多邊形定理，我們可以證明適用於任意連通平版圖的歐拉公式。

定理 2（連通平版圖的歐拉公式） 設 $M=(G,\beta )$ 為一直線平版圖，其中 $G$ 有限且連通。則 $M$ 恰有 $|E(G)|-|V(G)|+2$ 個面。

證明　對 $|E(G)|-|V(G)|$ 採用數學歸納法。由於 $G$ 連通，故 $|E(G)|-|V(G)|\ge -1\text{。}$

當 $|E(G)|-|V(G)|=-1$ 時，$G$ 是樹，故由定理 1 知 $M$ 具有 $$\begin{array}{r}1=(-1)+2=|E(G)|-|V(G)|+2\end{array}$$ 個面。

接著假設定理在 $|E(G)|-|V(G)|=k\ge -1$ 時成立，我們說明定理在 $|E(G)|-|V(G)|=k+1$ 時也成立。由於 $|E(G)|>|V(G)|-1\text{，}$故 $G$ 具有一環 $C\text{。}$設 $e=\{x,y\}\in E(C)\text{，}$並設 $H=G\setminus \{e\}\text{。}$由於 $\beta [e]\subseteq \beta [C]\text{，}$由喬登多邊形定理可知 $\beta [e]$ 的兩側在 ${\mathbb{R}}^2\setminus \beta [G]$ 中分屬不同的區域 $D\text{、}{D}^{\prime }\text{。}$由於在 ${\mathbb{R}}^2\setminus \beta [H]$ 中 $D$ 中的點均與 $D^{\prime }$ 中的點連通，故 $M=(G,\beta )$ 的面數比 $(H,\beta )$ 多 1。由此可知，$M$ 具有 $$\begin{array}{r}(|E(H)|-|V(H)|+2)+1=|E(G)|-|V(G)|+2\end{array}$$ 個面。定理得證。

參考資料

1. Reinhard Diestel. Graph theory. Springer, third edition, 2005.