一、前言

平面分割數問題是高中組合常見的問題, 例如 : 平面 $n$ 條相異直線(其中任兩條均不平行, 任三條均不共點), 可將平面分割成多少區域？ 解這類問題常用的方式是利用遞迴關係求解, 本文則是介紹平面圖枝理論 (planar graph theory) 中的歐拉公式來解這類型問題。

二、歐拉公式

圖枝理論始自 1736 年歐拉為解決哥尼斯堡七橋的路線問題所寫的一篇文章, 他把問題用點跟邊來描述並給出解決問題的充要條件。 在之後的兩百年間, 人們發現圖枝理論在社會與自然科學間有各式各樣的應用, 隨著近代資訊科學與網際網路的蓬勃發展, 它已經成數學中重要的一個分支。

一個圖枝 $G$ 是一個有序對 $(V,E)$, $V$ 是一個非空有限集, 它所包含的元素稱為頂點； $E$ 是一些 $V$ 的二元素子集所成的集合, 其元素稱為該圖枝的邊 。

為了方便起見, 我們常將邊 $\{u,v\}$ 寫成 $uv$。 舉例來說下圖 $G=(V,E)$ : $$V=\{a,b,c,d,e,f,g\},\qquad E=\{ab, ae,bc,bd,de,ef,fg\}$$

圖枝中的兩個頂點 $a,b$, 若存在交替的頂點和邊序列 $$\Gamma=(a=v_0,e_1,v_1,e_2,v_2,\ldots,e_n,v_n=b),$$ 其中 $v_0,v_1,\ldots,v_n$ 為頂點, $e_1,e_2,\ldots,e_n$ 為邊 且 $e_i\!=\!v_{i-1}v_i$, 則稱 $a,b$ 兩頂點是連通的。 如果一個圖枝中任兩頂點皆連通, 則稱此圖枝為連通圖枝。 由邊 (edge) 與頂點 (vertex) 所組成的一個圖枝 (graph), 若可以在平面上畫出來使得沒有邊相交, 則稱為平面圖枝 (planar graph)。

在了解了圖枝理論一些基本定義後, 下面的這個定理(歐拉公式)是我們計算平面區域數的主要計算工具, 它的敘述如下:

定理1() : 若一個連通平面圖枝 $G$ 有 $v$ 個頂點, $e$ 個邊, 並將平面分割成 $r$ 個區域, 則 $v-e+r=2$。

例如上圖為一連通平面圖枝, 頂點數 $v=7$, 邊數 $e=8$, 區域數 (含無限大區域) $r=3$, 所以 $v-e+r=2$。

本文中, 我們用歐拉公式來解決下列三個問題 :

1. 平面上有相異 $n$ 個圓(其中任兩圓有兩個相異交點、任三圓不共點), 將平面分割成多少個區域？
2. 平面相異 $n$ 條直線(其中任兩條均不平行, 任三條均不共點), 將平面分割成多少個區域？
3. 圓上有 $n$ 個相異點, 將其互相連接使得連接後圓內無三弦共點, 則可將圓的內部分成多少個區域？

三、歐拉公式解問題1

問題1: 平面上有相異 $n$ 個圓 (其中任兩圓有兩個相異交點、任三圓不共點), 將平面分割成多少個區域？

我們先考慮 3 個圓所形成的連通平面圖枝, 如下圖所示 :

我們分別計算它的頂點數與邊數 :

頂點數 ($v$) : 因任選兩圓有 2 個交點, 且任三圓不共點, 所以頂點數為 $2C_2^3=6$。

邊數 ($e$) : 因每個圓上的頂點數等於該圓的邊數, 而圖枝中每個頂點分屬兩個圓, 所以邊數為 $2v=12$。

由歐拉公式可知, 此圖形的區域數為 $r=2+e-v=2+12-6=8$。

對於一般的情形, 我們有如下定理 :

定理2() : 平面上有相異 $n$ 個圓 (其中任兩圓有兩個相異交點、任三圓不共點), 將平面分成 $n^2-n+2$ 個區域。

證明 : 因圖枝的每個頂點皆在圓上且任兩圓有共同交點, 所以圖形可視為一連通平面圖枝, 我們先分別計算圖枝的頂點數與邊數。

頂點數 ($v$) : 因任選兩圓有 2 個交點, 且任三圓不共點, 所以頂點數為 $2C_2^n$。

邊數 ($e$) : 因每個圓上的頂點數等於該圓的邊數, 又任三圓不共點, 故圖枝中每個頂點分屬兩個圓, 所以圖枝的邊數為 $2v=4C_2^n$。

由歐拉公式可知, 此圖形的區域數為 $r=2+e-v=2+4C_2^n-2C_2^n=n^2-n+2$, 得證。

四、歐拉公式解問題2

問題2: 平面相異$n$條直線 (其中任兩條均不平行, 任三條均不共點), 將平面分割成多少個區域?

我們先用一個例子來說明我們解題的思路 :

下圖 $G_1$ 是四條直線將平面分割的情況,

為了使用歐拉公式, 我們先將各直線以適當的線段來取代, 如下圖 $G_2$ 所示, $L_1,L_2,L_3,L_4$ 分別以 $\overline{AE}$, $\overline{BF}$, $\overline{DH}$, $\overline{CG}$ 取代 :

則它是一個連通平面圖枝。

我們計算 $G_2$ 的頂點數與邊數 :

頂點數 ($v$) : 因任兩條線段有一交點且無三線共點情形, 所以頂點數為 $C_2^4+2\times 4=14$。

邊數 ($e$) : 因取代直線後的各線段上的邊數為線段內交點數加 1, 例如 $\overline{AE}$ 上有 3 個交點, 這 3 個交點將 $\overline{AE}$ 分成 4 段, 又線段上每一交點分屬兩條線段 (如 $p_1$ 在 $\overline{AE}$, $\overline{DH}$ 上) 所以圖枝的邊數為 $2C_2^4+4=16$。

另一個計算方式是先計算一條線段上的邊數, 再計算總邊數。 因為任兩條線段有 1 個交點且無三線共點, 所以任一線段跟其他 3 條線段有 3 個相異交點, 這 3 個交點將線段分割成 4 個邊, 圖形一共有 4 條線段, 所以總邊數為 16。

由歐拉公式可知, 圖形 $G_2$ 的區域數為 $r=2+e-v=2+16-14=4$。 由於 $G_1$ 中的直線可無限延伸, 無限大的區域與 $G_2$ 的無限大區域不同, 因此必須做一些修正, 才能得到 $G_1$ 真正的區域數。 修正方式如下 :

扣除 $G_2$ 無限大區域後, 加回 $G_1$ 直線無限延伸所圍的區域, 例如 $Ap_1p_2B$, $Bp_2p_6C,\ldots$ 等, 共有 $2\times 4=8$ 個, 所以共有 $4-1+8=11$ 個區域。

對於一般的情形我們有如下定理 :

定理3() : 平面相異 $n$ 條直線 (其中任兩條均不平行, 任三條均不共點), 將平面分割成 $\dfrac{n^2+n+2}{2}$ 個區域。

證明 : 首先我們將原圖形 $G_1$ 的各直線以適當線段取代以保留原直線上的交點, 得圖枝 $G_2$, 因原圖形 $G_1$ 中任兩條直線均不平行, 所以任兩條直線必有一交點, 因此在 $G_2$ 中, 任兩條取代原直線的線段有一共同頂點, 而圖枝 $G_2$ 上的每個頂點皆在取代直線的線段上, 所以 $G_2$ 上任兩頂點必連通, 故 $G_2$ 為一連通平面圖枝。 接著我們計算圖枝 $G_2$ 的頂點數與邊數。

頂點數 ($v$) : 因任兩條線段有一交點且無三線共點情形, 所以頂點數為 $C_2^n+2\times n$。

邊數 ($e$) : 因取代直線後的各線段上的邊數為線段內交點數加 1, 又無三線共點, 故每一交點分屬兩條線段, 所以總邊數為 $2C_2^n+n=n^2$。

另一個計算方式是先計算一條線段上的邊數, 再計算總邊數。 因為任兩條線段有 1 個交點且無三線共點, 所以任一線段跟其他 $n-1$ 條線段有 $n-1$ 個相異交點, 這 $n-1$ 個交點將此線段分割成 $n$ 個邊, 圖形一共有 $n$ 條線段, 所以總邊數為 $n^2$。

由歐拉公式可知, 圖形 $G_2$ 的區域數為 $r=2+e-v=2+n^2-(C_2^n+2n)$。 由於 $G_1$ 中的直線可無限延伸, 無限大的區域與 $G_2$ 的無限大區域不同, 因此必須做一些修正, 才能得到 $G_1$ 真正的區域數。修正方式如下 :

扣除 $G_2$ 無限大區域後, 加回 $G_1$ 直線無限延伸所圍的區域共有 $2n$ 個, 所以共有 $2+n^2-(C_2^n+2n)-1+2n=\dfrac{n^2+n+2}{2}$ 個區域, 得證。

五、歐拉公式解問題3

問題3: 圓上有 $n$ 個相異點, 將其互相連接使得連接後圓內無三弦共點, 則可將圓的內部分成多少個區域？

這個問題在數學傳播第 63 期 中, 王子俠老師以遞迴關係與數學歸納法給出問題的答案, 我們使用歐拉定理重新證明。

先考慮圓上 5 點相連接形成的連通平面圖枝, 如下圖所示:

我們分別計算它的頂點數與邊數:

頂點數 ($v$) : 因為圓上任選四點相連可得一組相交的弦且圓內無三弦共點, 所以圓內頂點數為 $C_4^5$, 圖枝的頂點數為 $C_4^5+5=10$。

邊數 ($e$) : 圓內接五邊形共有 $C_2^5-5=5$ 條對角線, 各對角線的邊數為它的交點數加 1, 又圓內無 3 弦共點, 因此每一交點分屬兩條對角線, 所以對角線上的總邊數為 $2C_4^5+5=15$。 圓上相鄰頂點的邊的總數為 $2\times 5=10$, 所以圖枝的邊數為 $15+ 10=25$。

由歐拉公式可知, 此圖枝的區域數為 $r=2+e-v=2+25-10=17$。 扣除無限大區域 1, 所以圓內區域數為 16。

對於一般的情形, 我們有如下定理:

定理4() : 圓上有 $n$ 個相異點, 將其互相連接使得連接後圓內無三弦共點, 則可將圓的內部分成 $C_4^n+C_2^n+1$ 區域。

證明 : 因圓內任一頂點皆在圓的弦上, 又弦與圓相連接, 所以圖枝的任兩頂點連通, 因此我們可視本圖形為一連通平面圖枝。 先分別計算圖枝的頂點數與邊數。

頂點數 ($v$) : 因為圓上任選四點相連可得一組相交的弦且圓內無三弦共點, 所以圓內頂點數為 $C_4^n$, 圖枝頂點數為 $C_4^n+n$。

邊數 ($e$) : 圓內接 $n$ 邊形共有 $C_2^n-n$ 條對角線, 各對角線的邊數為它的交點數加 1, 又圓內無 3 弦共點, 因此每一交點分屬兩條對角線, 故對角線上的總邊數為 $2C_4^n+C_2^n-n$。 圓上相鄰頂點的總邊數為 $2\times n$, 所以圖枝的邊數為 $2C_4^n+C_2^n+n$。

由歐拉公式可知, 此圖枝的區域數為 $$r=2+e-v=2+(2C_4^n+C_2^n+n)-(C_4^n+n)=C_4^n+C_2^n+2.$$ 扣除無限大區域 1, 所以圓內區域數為 $C_4^n+C_2^n+1$, 得證。

六、結語

問題 1, 2 是高中課本常見的組合問題, 基本的做法是建立它的遞迴關係來解出問題的答案。 本文介紹的歐拉公式是解決這類問題的另一個方式, 它在兩百多年前由歐拉所發現, 這公式說明了一個連通平面圖枝中點的個數、 邊的個數以及區域數所存在的一個關係。 因此, 只要圖形可化為連通平面圖枝, 在計算完它的頂點數與邊數後, 我們就能藉由歐拉公式得到它的區域數。

參考資料

---本文作者任教彰化藝術高中---