為甚麼把邊換成路徑?
歐拉(Euler)公式給出的邊數界能迅速證明一些圖非平面,但稀疏圖可能通過這些檢驗。例如,把 的每條邊都換成兩條邊組成的路徑,原來的連接關係仍在,新增的九個頂點卻令邊數界寬鬆得多。要把這個直覺變成證明,必須準確說明哪些路徑替代了哪些邊,以及插入或消去路徑內部頂點為何保持平面性。
本節的圖均為有限簡單無向圖。
定義 3.2.1
(細分與分支頂點)
圖 的一個細分是把每條邊 換成一條正長度的 – 路徑所得的圖;這些替代路徑的內部頂點兩兩不相交,且都不是 的原有頂點。長度為一表示該邊不變。原有頂點稱為分支頂點。每條替代路徑的內部頂點在細分圖中度數為二;若細分圖處於一個更大的圖中,這些頂點在大圖中可以有額外的邊。
定理 3.2.2
(細分保持平面性)
有限簡單圖 平面,當且僅當它的任意細分 平面。
證明
(在弧上標點與連接弧)
若已有 的平面嵌入,就在每條邊弧的內部標出所需數目的不同點作為新頂點;所得的 仍沒有交叉。
反過來,設 已有平面嵌入。對每條替代路徑,把其連續的邊弧合看為連接兩個分支頂點的一條弧,並不再把內部點視為頂點。路徑沒有重複頂點,所以這條拼接弧是簡單弧。不同替代路徑內部頂點互不相交,嵌入中的邊也沒有交叉,因此這些弧只可能在共同的分支端點相遇。所得圖形恰好是 的平面嵌入。未細分的邊和孤立頂點也沒有問題。
證明透視
反方向為何成立
正方向只是在弧上標點。反方向才用到細分的定義,而定義的每一項各有作用。替代路徑沒有重複頂點,使連接起來的弧是簡單弧,而不是與自身相交的曲線。內部頂點兩兩不相交,加上 的嵌入沒有交叉,使兩條連接弧只在共同分支頂點處相遇。內部頂點都不是 的原有頂點,則防止一條弧穿過分支頂點。若去掉內部不相交的條件,論證就在第二項失效:在下面反例的星圖中,九條路徑都經過同一個頂點,它們連接後的弧會在那裏相遇。
推論 3.2.3
(非平面性的細分證據)
若圖 含有一個子圖,它是某個非平面圖 的細分,則 非平面。
證明
(把嵌入限制到子圖)
由定理,細分 非平面。若 有平面嵌入,刪去 以外的頂點和邊便得到 的平面嵌入,矛盾。
實際寫出證據時分兩步。先指定子圖 :列出分支頂點,對 的每條邊給出一條對應路徑。再核對不同路徑沒有共同內部頂點、路徑內部也沒有分支頂點。大圖裏的額外邊可以不選入證據;子圖不必是誘導子圖。
僅指出若干頂點之間都有路徑並不足夠:必須列出路徑並檢查互不相交的條件。另一方面,兩所選頂點之間的額外邊只要不選入子圖,就不影響證據。
消去度為二的頂點到底做了甚麼?
逆向證明並不要求移動曲線。細分圖嵌入中的每條邊都是弧;替代路徑的相鄰邊弧只在共同端點相接。因此,它們的並是一條弧,中間的度二頂點現在只作為弧上的普通點。這稱為消去這些頂點。由於沒有其他所選邊經過內部頂點,不會產生新的交點。若該點在大圖中還接有額外邊,應先捨去這些邊:消去操作作用於所選子圖,不一定作用於整個大圖。
反過來看,沿一條邊插入一個頂點, 和 各增加一。因此 減少二, 減少一。反覆細分會讓這些必要的邊數界更容易滿足,卻不改變平面性。使用二部圖的界之前必須另行核對二部性:只細分一條邊可能破壞它,例如四邊形會變成五邊形。若每條邊都細分一次,原頂點和新頂點分別構成兩部,所得圖一定是二部圖。
細分與圖的子式
定義 3.2.4
(圖的子式)
圖的子式(minor)可透過刪除頂點、刪除邊及收縮邊得到;回到簡單圖時刪除自環並合併重邊。
每個 的細分都以 為子式:在每條替代路徑上收縮除一條以外的所有邊,但不把兩個分支頂點合併。內部不相交保證各條路徑可獨立處理。反過來不成立:取相鄰的兩個三度頂點,各自再接兩個葉子。收縮連接這兩個頂點的邊,得到 。但原樹的最大度為三,不可能含有 的細分,因為後者的中心對應頂點須接出四條不同路徑的首邊。因此子式證據與細分證據的核查要求不同。
一個稀疏障礙
例題 3.2.5
(細分 的每一條邊)
設 的兩部為 和 。對每個跨部頂點對 ,引入不同的新頂點 ,用 替換邊 。所得圖 有 個頂點和 條邊。六個原頂點是分支頂點,九條路徑的內部頂點各不相同;所以 是非平面的 的細分,也非平面。
普通平面圖邊數界允許 ;二部平面圖的更強界也允許 。事實上, 是二部圖:一部取六個原頂點,另一部取九個新頂點。這兩個不等式都未檢測出障礙。再加入只與 相鄰的新葉子 和額外邊 ,所得大圖仍非平面:刪去葉子與額外邊後,證據 仍在。
反例模式
共用內部頂點的路徑不足夠
取六個頂點 和第七個頂點 ,只把 分別連到其餘六點。每個跨部頂點對都有一條如 的路徑,但九條所提路徑都共用內部頂點 ,並不構成 的細分。實際上此圖是一棵星形樹,完全可以平面嵌入。若不檢查內部不相交,路徑存在性不能證明非平面。
寫出兩份可核對的證據
例題 3.2.6
(額外邊中隱藏的 細分)
取分支頂點 ,加入路徑 和 ,其中 為互不相同的新頂點。其餘八個分支頂點對直接用邊 相連。再加入邊 。這十條所需路徑中,兩條的內部頂點集分別是 、,其餘八條沒有內部頂點,因此符合細分條件。選取證據子圖時捨去 。所選子圖是 的細分,故整個圖非平面。大圖共有八個頂點:五個分支頂點和三個內部頂點;列出的十條路徑證明任何畫法都不能成為平面嵌入。
例題 3.2.7
(路徑長度不等的 證據)
取兩組分支頂點 和 ,使用以下九條路徑:
設 為六個不同頂點,且都不在分支頂點中。還可加入邊 。九條路徑恰好對應九個跨部頂點對,其非空內部頂點集為 、、、 和 ,兩兩不相交。所選子圖不包含額外邊 ,所以即使大圖中兩個內部頂點還有額外邊,它仍是 的細分證據。所選子圖有十二個頂點和十五條邊;普通平面邊數界允許 ,僅憑這個計數無法斷定平面性。
實際尋找證據時,可以先找度數足夠的候選分支頂點,再追蹤連接路徑。畫圖時消去看似度二的鏈可以提示基本圖,但最後仍應列出路徑。尤其是,度數本身不能證明細分存在;大圖中的分支頂點也可以有額外鄰點。
旁註
在稀疏圖中先試二部障礙
細分需要五個度至少為四的分支頂點,而 細分只需要六個度至少為三的分支頂點。若度為四的頂點很少,應先找 。
證據能說明甚麼
和 的非平面性可由歐拉公式的邊數界證明。以上論證給出一個方向:含有其中任一圖的細分的圖必非平面。它本身並未證明每個非平面圖都含有這樣的細分;後者是更深的 Kuratowski 定理,本節不證明。找不到證據不等於找到了平面嵌入,通過邊數檢驗也不等於平面。要證明平面性,可以給出無交叉嵌入或其他有效論證。
細分是沿邊插入度為二的頂點,與在大圖中任意收縮一條邊不同。圖形可以幫助發現證據,最終仍應寫出可核對的路徑。
常見錯誤
(度數本身不能證明細分存在)
高度數只能提示候選分支頂點,並不能證明甚麼。八面體圖可畫成三角形 圍住三角形 ,其中 連到 , 連到 , 連到 ;這個畫法說明它是平面圖,但它的六個頂點度數都是四。任取五個頂點都通過 分支頂點的度數檢驗,然而平面圖不可能含有 的細分。
常見錯誤
(通過邊數檢驗不等於平面)
有 個頂點、 條邊的細分 同時滿足 與 ,卻非平面。邊數界只是必要條件;要證明平面性,應給出嵌入。
練習
快速檢查
(將 的一條邊細分一次。計算頂點數和邊數,檢查普通平面邊數界,並證明所得圖非平面。)
解答 · 答案
頂點有六個,邊有十一條:刪去一條邊再添兩條,邊數由十增至十一。邊數界允許 。但消去新增的度二頂點便恢復 ,由細分保持平面性可知所得圖非平面。
快速檢查
(一個圖含有 的細分,又在不同替代路徑的兩個內部頂點之間加了一條邊。為甚麼額外邊不破壞證據?)
解答 · 答案
選取原來的細分路徑,不把額外邊選入子圖。所選路徑的內部頂點仍兩兩不相交,故所選子圖仍是 的細分;這些頂點在大圖中的度數並不妨礙此證明。
快速檢查
(從兩部為 和 的 刪去邊 。描述一個平面畫法,並說明為甚麼這不與 非平面矛盾。)
解答 · 答案
畫出三條內部不相交的路徑 、 和 ,形成平面上的三個弧形區域。在第一、二條路徑之間的一個面中放入 ,在該面內分別連到 和 ,不產生交叉。這恰是 。刪除邊可能使非平面圖變為平面圖;非平面性從子圖傳給超圖,不能反向推。
快速檢查
(有人聲稱把平面圖的一條邊細分一次可能產生非平面圖。指出錯誤並解釋正確結論。)
解答 · 答案
在原平面嵌入的一條邊弧內部標出新頂點,即得所需細分,且不會產生交叉。因此細分後的圖仍平面。另一個有交叉的畫法不能否定這個無交叉嵌入的存在。
快速檢查
(構造一個以 為子式、卻不含 細分的圖,並證明這兩點。)
解答 · 答案
將兩個三度頂點相連,各自再接兩個不同的葉子。收縮中間邊得到一個中心連著四個葉子的 。原圖最大度為三,而任何 細分的中心必須接出四條不同路徑的首邊,所以原圖不含這樣的細分。