【離散數學】平面圖：planar graph

• planar graphs
  
  
  若一個 graph G 可以畫出一個兩兩 edge 不相交的平面圖，則我們說他是一個 planar graph。而這種不相交的畫法就稱為 G 的 plane graph。
  
  
  一個 planar graph 可以有許多 plane 畫法。

• 圓弦法
  
  
  我們假設圖形可平面化，首先找出最長的一條 circuit ，畫成一個圓，再將其餘連線加上去，我們將其餘的連線稱為弦，第一條弦可以任意選取，他可以被畫在圓外或圓內，( 因為圓的特性，這兩種情形其實沒有差別 )，而根據第一條弦的畫法，可能有某條弦只能有一種畫法才能不相交，如此不斷畫下去，若有一條弦無論怎麼畫都會與其他連線相交，則此圖就不可平面化，而若是成功畫完，就證明了這個圖可平面化。

• Euler's formula：r - e + v = 2
  
  
  若 G 是一個 connected planar graph，則對於 G 的任意 plane graph ，r - e + v = 2 這個式子皆會成立。其中 r 代表平面圖中區間的數量，包含有界區間與無界區間，而 e 則是邊的個數，v 為頂點的個數。
  
  
  使用數學歸納法證明。我們在維持圖形 connected 的情況下，慢慢將連線與頂點加入，當只有一個 edge 時，只有一個區域、一個連線、兩個頂點，尤拉公式成立，而我們發現，當有 n-1 條 edges 時，再加入一條連線只有兩種方法，在已有的圖中找兩點相連，或是原圖中一點與新加入一點相連。而在第一種方式中，兩個頂點必在同一個區域的邊界上( 否則不為平面圖 )，因此新的連線會產生一個新的區域，尤拉公式成立。而第二種方式，則是增加一個頂點與一條連線，不增加區域，尤拉公式亦成立。

• degree of region
  
  
  一個區域的 degree 為這個區域的邊界上連線的個數，而每一個連線可能同時是兩個區域的邊界，或者在同一區域的邊界中出現兩次，在第二種情形時則此連線對於 degree 的貢獻要算兩次。
  
  
  如此一來一個平面圖所有區域的 degree 數相加正好會是其 edges 數的兩倍。
  
  幾乎所有區間的 degree 都會大於等於三，只有 e=1 時的無界區間 degree 為 2。

• cor
  
  
  若一個 connected planar graph 的 e > 1 ，則 e <= 3v - 6。
  
  
  我們知道，當 e > 1 時，每個區間的 degree >= 3，且 degree 和會等於 2e，因此 2e >= 3r，帶入尤拉公式，就得到我們的引理。
  
  
  若一個 bipartite connected planar graph 的 e > 1 ，
  則 e <= 2v - 4。
  
  
  我們知道，bipartite 裡的每一個迴圈長度都會是偶數，而每個區間的邊界正是一個迴圈，因此每個區間的 degree >= 4，再帶入尤拉公式，即可得此引理。

• Thm
  
  
  一個 graph G 為 planar graph 若且惟若 G 不擁有由 K5 或 K3,3 的 configuration 所構成的 subgraph。
  
  
  K5 為擁有五個頂點且任兩點皆有連線的圖，K3,3 則是由兩個 3 頂點的 bipartite arrangement 組成的 complete bipartite graph，而 configuration 指的是在這樣的圖的邊上加上點後形成的圖，例如原本為 (a,b) 加入 c 點後變成 (a,c) 與 (c,b)。
  
  K5 與 K3,3 本身皆不可平面化，因此擁有它們作為子圖的圖必不可平面化，我們可以發現 configuration 並不會使他們從不可平面化變為可平面化。
  
  對於不可平面化的圖，我們可以使用圓弦法找到這些子圖。

• 塗色問題與四色定理
  
  
  塗色問題是一個經典的平面圖問題，問的是：若要在一張地圖上塗色，相鄰的國家顏色必須不同，則最少用幾種顏色可以達成目標，而四色定理正式說明用四種顏色可以達成。將每個國家視為一點，若兩國家相鄰則此兩點連線，我們可以將這個問題轉換為平面圖的模型，這樣取得的圖形我們稱之為 dual graph 。
  
  由 K5 不可平面化可看出，不可能存在兩兩相臨的五個國家。