拓樸圖論簡介 拓樸圖論(Topological Graph Theory)主要是研究如何把一個圖適當地畫在曲面(Surface)上，使得任意圖上的兩邊，除了端點之外，都沒有其他相交的點。例如： 可以畫在球面上滿足上述的要求，而 就辦不到。

Presentation on theme: "拓樸圖論簡介 拓樸圖論(Topological Graph Theory)主要是研究如何把一個圖適當地畫在曲面(Surface)上，使得任意圖上的兩邊，除了端點之外，都沒有其他相交的點。例如： 可以畫在球面上滿足上述的要求，而 就辦不到。"— Presentation transcript:

1 拓樸圖論簡介 拓樸圖論(Topological Graph Theory)主要是研究如何把一個圖適當地畫在曲面(Surface)上，使得任意圖上的兩邊，除了端點之外，都沒有其他相交的點。例如： 可以畫在球面上滿足上述的要求，而 就辦不到。

2 拓樸模式(Topological Model)
當我們把圖畫在曲面上，圖中的每一邊都可以看成是空間中的一條封閉曲線(含頂點)，簡稱為空間中的曲線。這裡的空間是指3-維歐式空間。 定義1.1（Space Curve） 一條連接u與v兩點的曲線可以看成是一個連續函數 的值域，這裡的f是1-1函數，而且 以及 ；在u=v的情況下 是1-1函數。

3 定義1.2（Topological Model）
經由拓樸模式所畫出來的圖直接用原圖Ｇ稱之。也就是說，把一般圖Ｇ想像成是已經畫在3-維空間中，同時滿足拓樸模式的規定，邊與邊之間，除了端點之外其他部分皆不相交。

4 定義1.3（Sphere） 一個球面是一個3-維歐式空間的集合，它包函所有的點 滿足 ，r是一個正實數。 刻劃一個曲面是否為球面的最著名定理非喬丹曲曲線定理莫屬。 定理1.4（Jordan Curve Theorem） 在球面（或平面）上的簡單封閉曲線（Simple Closed Curve）把球面（或平面）分隔成兩部份，也就是說在球面上（或平面上），任意連接不同部分中兩點的曲線必然與這封閉曲線相交。

5 定義1.5（Dount） 一個標準的甜甜圈（Standard Dount）是一個半徑為1的圓盤，以(2,0)為中心，繞著y軸旋轉所得到的曲體（Solid），如圖1.1所示 圖1.1:標準甜甜圈

6 一個標準甜甜圈的表面稱為是輪胎面（Tours）。
一個輪胎面不是球面，這可以利用喬丹曲線定理加以證明：因為，在輪胎面上，我們可以找到一個簡單封閉曲線Ｄ，他無法將輪胎面分個成兩部份，如圖1.2中的Ｃ及Ｄ兩條封閉曲線。 圖1.2：Torus

7 一個莫比斯帶是由一個長方形帶經過扭轉（如圖1.3）後再連接所獲得的帶狀曲面。
定理1.7（Mobius Band） 一個莫比斯帶是由一個長方形帶經過扭轉（如圖1.3）後再連接所獲得的帶狀曲面。 圖1.3：Mobius Band

8 曲面（Surface） 在這一節中，我們將明確地定義曲面是什麼，同時也對於曲面的分類做進一步說明。
定義2.1（Topological Equivalence, Homeomorphism） 一個由X映至Y的連續函數f為一拓樸等價函數若且為若f是1-1，映成而且　　也是連續函數，此時Ｘ與Ｙ稱為是拓樸等價。 定義2.2（Surface） 一個曲面（Surface）是指一個在3-維歐式空間中的一個集合，它滿足對於集合中的每一個元素x，都存在一個鄰域（Neighborhood），它與下列兩個集合之一拓樸等價： （a）　　　　　　　　　 ， （b）　　　　　　　　　　　　 。

9 上述定義中的稱為 開單位平面圓盤，而 則是標準的半圓盤（Standard half-disk）。在曲面中具有鄰域與 拓樸等價的點稱為是內點（Interior point），不然是邊界點（Boundary Point）。 定義2.3（Boundaryless Surface） 每個點都是內點的曲面稱為無邊界曲面，例如歐式平面。 定義2.4（Closed Surface） 滿足下列條件的連通曲面稱為封閉曲面： （a）S是有限的，即存在一個球體B，使得 。 （b）S是無邊界曲面。 （c）如果 ，則 及 都在S中。

10 命題2.5 球與輪胎均為封閉曲面，而平面與莫比斯則不是。 證明：省略 定義2.6（Non-orientable Surface） 一個曲面如果它包含了一部份（部份曲面）與莫比斯帶拓樸等價，則此曲面稱為是一個不可定向的曲面。 定義2.7（Orientable Surface） 不是不可定向的曲面稱為是可定向曲面。

11 我們用　代表球面。然後再依遞迴方式建構　，它是在　 這個曲面上再加入一個把手（handle）所形成的曲面，參考圖2.1 。
定理2.8（Gross及Tucker）（可定向封閉曲面的分類） 每一個可定向封閉曲面必定和 之一的曲面拓樸等價。

12 一個封閉曲面的虧格（Genus）就由它所等價的 所決定，亦即虧格是k。所以球面的虧格是”0” ，而輪胎面的虧格是”1” 。在另一方面，不可定向封閉曲面的分類也可利用加入跨蓋（Crosscap）的方式獲得。 首先，定義球面（ ）為 ，也就是說開始建構的基礎一樣；再利用莫比斯帶，如圖，將它接在 的一個圈上即得 ；加入的管稱為是跨越蓋（Crosscap），如圖2.2。 圖2.2：加Crosscap

13 定理2.9（Gross及Tucker） （不可定向封閉曲線的分類） 一個不可定向的封閉曲面必定與 之一拓樸等價。 同上理由，與 拓樸等價的不可定向封閉曲面，它的不可定向虧格（Non-orientable Genus）為k，也就是加入跨越蓋的個數為k。 作業： 如何畫?

14 曲面的多邊形表示法 從輪胎面（Torus）的形狀，我們不難想到利用依長方形紙片即可做出這個曲面。如圖3.1所示，首先將 與 黏合（照箭頭的方向依序黏合）。如此一來可以得到一圓筒，然後再將圓筒的兩側按 的方位依序黏合即可獲得一個輪胎面。 圖3.1：輪胎面

15 圖3.2：Klein瓶

16 (Projective plane)

17 代表何種曲面？

18 圖的正規畫法與圖的嵌入 由圖在空間的拓樸模式，我們不難發現以下三種可以避免的現象： （a）兩點畫在同一個位置。 （b）一個邊跨越自己， 。
（c）一個邊通過另一個不在邊上的點。 除了上述現象之外，尚有其他三種不是正規的現象： （d）兩邊（端點除外）有兩點以上的交點。 （e）兩邊所對應的曲線相切， 。 （f）三條邊交於一點， 。

19 在畫圖中，兩個不同邊所共同使用的點（端點除外）稱為是該圖的一個跨越（Crossing）。
定義4.1（圖的嵌入， Graph Embedding of Graph imbedding） 一個圖嵌入於一個曲面Ｓ是指將Ｇ畫在曲面Ｓ上使得它沒有任何的跨越；也就是說，把Ｇ的拓樸模式利用一個拓樸等價（Homeomorphism）把它對應到Ｓ的一個子集合。 定義4.2（平面圖，Planar Graph） 一個可以嵌入在平面上的圖稱為是平面圖。 定義4.3（球面圖，Spherical Graph） 一個可以嵌入在球面上的圖稱為是球面圖。

20 定義4.4（Region） 對應於一個把Ｇ嵌入在曲面Ｓ上，一個區域（Reggion）是指在Ｓ中把Ｇ的值域扣除之後的部份（Component），亦即最大的連通部分。 　　直觀來說，當Ｇ嵌入在Ｓ上之後，在Ｓ中拿掉Ｇ的點與邊所剩的一些部份就是區域。如果這時候每個區域都和依個開放的單位圓（Open Disc）拓樸等價，則這樣的嵌入稱為是圓盤嵌入。

21 Ｇ： （ａ） 2-花束 （ｂ） 圖4.1：輪胎面上的花束

22 命題4.5 任意不連通的圖都不可能有圓盤嵌入。 證明：必定存在一個區域它無法與開放原盤拓樸等價（？）。 有了區域之後，我們可以定義一個圖嵌入的面（Face）。 定義4.6（Face 及 Face Set） 一個圖嵌入中的一個區域與此區之邊界的聯集就稱為是此圖嵌入的一個面。所有面所成的集合稱為是面集合，以Ｆ表示。若是這個面集合是把Ｇ嵌入所得到的面集合，則以 表示。

23 命題4.7 　　令Ｇ嵌入在一個平面上，同時一個邊e它兩次出現在嵌入中的一個面上，則這個邊必定是橋。 證明： 　　令x為e的內點。則以x為起點找到一條封閉曲線繞著接下來出現的邊走到再出現e時連接x；這個封閉曲線所圍的子圖將在e邊去掉之後與其它部分不連通（？）。

24 　　在這裡補充說明，上述出現兩次的邊，在適當地指定方向（繞著邊界）之後造成每個邊都出現兩次，而兩次的方向剛好相反。可以辦到的嵌入也稱為是可定向的嵌入（Orientable Embedding）。例如圖4.2的例子可以將前進的方向在 中取逆時針，於四個面周界繞行方式如下： ， ， ， 。 圖4.2： 的嵌入

25 圖的虧格（The Genus of a Graph）
首先，我們知道曲面可以分成可定向及不可定向兩種，因此，圖的虧格也分成兩種。 定義5.1 圖Ｇ的可定向虧格（Orientable Genus）簡稱虧格，　 ，是指Ｇ可以嵌入所有可定向曲面中，虧格最小的曲面之虧格（把手數）。而不可定向虧格（Non-orientable Genus）， ，則可嵌入的所有不可定向曲面中，跨越蓋數最少的曲面所用的跨越蓋數。

26 例：　　　　　　　　　。（參考下圖） 圖5.1：　 嵌入於輪胎面上

27 以下討論圖嵌入的性質，在圖中重且及弧圈都是容許的，也就是說圖可以是擬圖（Pseudograph）。
定理5.2 令Ｇ為一（p,q）-圖，同時它被圓盤嵌入在一個虧格為n的曲面上，則p-q+r=2-2n，其中r為區域數。 證明：參考下圖。

28 切割處 切開之後

29 切開（填平缺口）

30 　　上述定理說明了圓盤嵌入的特性，當然對於沒有重邊或弧的圖，上述的等式也自然成立。現在，再利用Youngs所提供的拓樸證明，唬的虧格就可以利用p,q,r表示出來。
定理5.3（Euler-Poincare） 設Ｇ為嵌入於虧格　　而且有r個區域的曲面上之（p,q）-連通圖，則　　　　　　　　。

31 定理5.4（Ringel及Youngs） 　　　　　　　　　　。 定理5.5（Ringel） 如何求圖的虧格： 敬請期待！