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

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

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

圓上有 $n$ 個相異點, 將其互相連接使得連接後圓內無三弦共點, 則可將圓的內部分成多少個區域？ 為了使用歐拉公式, 我們先將各直線以適當的線段來取代, 如下圖 $G_2$ 所示, $L_1,L_2,L_3,L_4$ 分別以 $\overline{AE}$, $\overline{BF}$, $\overline{DH}$, $\overline{CG}$ 邊數 ($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$ 個區域。 對於一般的情形我們有如下定理 : 首先我們將原圖形 $G_1$ 的各直線以適當線段取代以保留原直線上的交點, 得圖枝 $G_2$, 因原圖形 $G_1$ 中任兩條直線均不平行, 所以任兩條直線必有一交點, 因此在 $G_2$ 中, 任兩條取代原直線的線段有一共同頂點, 而圖枝 $G_2$ 上的每個頂點皆在取代直線的線段上, 所以 $G_2$ 上任兩頂點必連通, 故 $G_2$ 為一連通平面圖枝。 接著我們計算圖枝 $G_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}$ 個區域, 得證。 邊數 ($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。 對於一般的情形, 我們有如下定理: 邊數 ($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 是高中課本常見的組合問題, 基本的做法是建立它的遞迴關係來解出問題的答案。 本文介紹的歐拉公式是解決這類問題的另一個方式, 它在兩百多年前由歐拉所發現, 這公式說明了一個連通平面圖枝中點的個數、 邊的個數以及區域數所存在的一個關係。 因此, 只要圖形可化為連通平面圖枝, 在計算完它的頂點數與邊數後, 我們就能藉由歐拉公式得到它的區域數。 海龜按照某固定規則平面移動所形成軌跡問題的探討。 高中數學學科中心電子報, 148 期, 2019.07。 許閎揚。 平面上頂點用直線相連後的區域數公式。 高中數學學科中心電子報, 149 期, 2019.08。 R. Brualdi, Introductory Combinatorics . 5$^{\rm th}$ ed., Pearson, 2009. R. Graham, D. E. Knuth, O. Patashnik. (1994). Concrete Mathematics : A Foundation for Computer Science . Addison-Wesley Professional, 2nd edition, 1994.

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

聯絡方式: 106319 台北市羅斯福路四段1號 天文數學館6樓 中央研究院數學研究所數學傳播編輯部

電話:02-23685999 轉 382 | 傳真: 02-23689771 | Email: media@math.sinica.edu.tw
網路平台: 數學所資訊室 | Tel:02-23685999 轉 743 | Email: ytlin@math.sinica.edu.tw
© 2017 中央研究院數學研究所 All rights reserved.