平面圖檢查器

平面圖檢查器

平面圖檢查器判定一個簡單無向圖是否為平面圖（即可畫在平面上且任意兩條邊不相交），當圖形未通過測試時，它會尋找並視覺化 Kuratowski 證明：即 K₅（5 個頂點的完全圖）或 K₃,₃（3 + 3 個頂點的完全二部圖）的細分。此工具專為教學、競賽編程熱身以及快速驗證小型圖形結構而設計。

什麼是「平面圖」？

如果一個圖 G = (V, E) 可以嵌入平面中，使得邊僅在其共享端點處相遇（無交叉），則該圖是平面的。等效地，G 可以畫在球面上而沒有交叉。平面性是一個純粹的拓撲屬性：它不取決於您如何繪製圖形，而僅取決於是否存在某種無交叉的畫法。

平面圖隨處可見 —— 道路和公用事業網絡、印刷電路板 (PCB) 佈線、柏拉圖立體的邊圖以及多面體的面結構。然而，許多「自然」產生的圖形卻是非平面的：任何時候當您嘗試將 3 棟房屋連接到 3 種公用事業（水、電、氣）而沒有交叉時，您都會遇到 K₃,₃ 障礙。

Kuratowski 定理 —— 檢查器的核心

Kazimierz Kuratowski 在 1930 年證明了平面性具有純粹的組合特徵：

圖 H 的細分是通過將 H 的某些邊替換為更長的路徑（其內部頂點都是新的度為 2 的頂點）而獲得的。因此，Kuratowski 定理指出 K₅ 和 K₃,₃ 是平面性的唯一障礙 —— 每個非平面圖都以「拉伸」的形式包含其中之一。

禁用圖

Euler 公式與快速必要條件

在運行（相對昂貴的）細分搜索之前，檢查器會應用兩個源自 Euler 公式的快速必要條件：對於在平面中繪製的任何連通平面圖，具有 V 個頂點、E 條邊和 F 個面（包括無界的外部面），我們有

結合簡單平面圖的每個面邊界至少有 3 條邊的觀察，我們得到了邊數上限：

任何違反這些不等式的圖形立即被判定為非平面，無需進行細分搜索。K₅ 有 m = 10, n = 5 ⇒ 3n − 6 = 9，因為 10 > 9，違反了界限。K₃,₃ 有 m = 9, n = 6 ⇒ 2n − 4 = 8，因為 9 > 8，違反了二部圖界限。

細分搜索的工作原理

在進行廉價的 Euler 檢查後，檢查器會直接搜索細分：

1. 快速獲勝 —— 將 K₅ 或 K₃,₃ 作為文字子圖進行檢測。 如果 5 個頂點兩兩相鄰，那就是 K₅。如果 6 個頂點分為 3 + 3 且所有 9 條跨組邊都存在，那就是 K₃,₃。
2. K₅ 細分搜索。 對於每組候選的 5 個「分支」頂點（在 G 中的度數均 ≥ 4），嘗試尋找 10 條路徑 —— 每對分支一條路徑 —— 這些路徑是內部頂點不相交的（除分支頂點外，任何頂點都不會出現在多條路徑中），並且避免使用其他分支作為內部頂點。一旦找到即證明非平面性。
3. K₃,₃ 細分搜索。 選取 6 個分支（度數均 ≥ 3）和一個 3 + 3 的二部劃分。搜索具有相同內部不相交要求的 9 條跨組對路徑。
4. 無證明 ⇒ 平面圖。 如果在大小限制內未找到任何細分，Kuratowski 定理保證該圖是平面圖。

尋找頂點不相交路徑通常是 NP 困難的，因此檢查器使用有界隨機貪心搜索：每次迭代按難度對所需的頂點對進行排序，首先使用隨機 BFS 為最難的頂點對選取一條路徑，移除這些內部頂點，然後繼續。如果該特定順序失敗，它會使用隨機化順序重試 —— 每個分支配置最多重試 40 次。在所有測試過的小型圖（最多 16 個頂點）中，這足以在證明存在時找到它。

如何使用此計算機

1. 使用頂部的標籤選擇輸入格式：邊列表或鄰接列表。兩者編碼的是相同的圖形。
2. 輸入您的圖形。圖形被視為無向圖，因此 A-B 和 B-A 是同一條邊。
3. 點擊檢查平面性。工具會報告判定結果，顯示分步推理（Euler、二部、Kuratowski），並渲染圖形。
4. 對於非平面圖，視覺化會對 K₅ 或 K₃,₃ 細分著色，並列出 10 條（或 9 條）頂點不相交路徑。點擊路徑行可將其單獨顯示。
5. 對於平面圖，會報告面數 F = m − n + 1 + c 以及圖形結構。

應用示例 1 —— K₄ 是平面圖

K₄ 有 n = 4，m = 6。任何頂點數 ≤ 4 的圖都是平面的，事實上 K₄ 可以嵌入為一個三角形，其內部有一個頂點連接到所有三個角。Euler 公式指出 F = 6 − 4 + 2 = 4 個面：三個三角形內部面加上一個外部面。

應用示例 2 —— K₃,₃ 是非平面圖

K₃,₃ 有 n = 6，m = 9。它是二部圖，因此適用二部圖界限：m = 9 > 2n − 4 = 8。僅此一項就證明了非平面性。其證明是顯而易見的 —— K₃,₃ 本身就是禁用子圖。工具隨後會突出顯示 3 + 3 劃分和 9 條直接邊。

應用示例 3 —— Petersen 圖

Petersen 圖有 n = 10，m = 15，因此 m ≤ 3n − 6 = 24，快速 Euler 檢查通過。然而它卻是著名的非平面圖。檢查器定位出一個 K₃,₃ 細分：從外部五邊形和內部五角星中選取六個頂點，使得每個跨組對都可以通過剩餘的四個頂點經由頂點不相交路徑進行路由。工具繪製出該證明，使 1930 年代的幾何理論變得觸手可及。

平面性的應用

• VLSI 和 PCB 佈線。 只有當連接圖是平面時，單層電路才可行；非平面網絡強制使用過孔或額外層。
• 圖形繪製與視覺化。 平面圖允許清晰、無交叉的佈局 —— 對於地鐵路線圖、調用圖和示意圖非常有用。
• 算法設計。 許多 NP 困難問題（最大割、頂點覆蓋、圖同構）在限制於平面圖時變為多項式時間問題。
• 圖形著色。 四色定理保證每個平面圖都是 4 色的 —— 這是一個經典結論，其陳述取決於平面性。
• 組合優化。 平面最短路徑、最大流和最小割都具有專門的快速算法。
• 分子化學。 苯環芳香烴圖是平面的；某些籠狀分子則不是。

常見問題解答

對於圖形來說，「平面」是什麼意思？

如果一個圖可以畫在平面上，使得任意兩條邊除了在共享頂點外不互相交叉，則該圖是平面的。等效地，一個圖是平面的當且僅當它可以畫在球面上而沒有交叉。樹、環、立方體圖和柏拉圖立體都是平面的，而 K₅ 和 K₃,₃ 是典型的非平面例子。

什麼是 Kuratowski 定理？

Kuratowski 定理指出，一個有限圖是平面的當且僅當它不包含作為 K₅ 或 K₃,₃ 細分的子圖。細分是通過將某些邊替換為更長的路徑（每條路徑通過全新的度為 2 的頂點）而獲得的。這提供了一個具體的非平面性組合證明。

K5 和 K3,3 有什麼區別？

K₅ 有 5 個頂點，每一對頂點都由一條邊連接，總共有 10 條邊。K₃,₃ 有 6 個頂點，分為兩組各 3 個，其中一組的每個頂點都與另一組的每個頂點相連，總共有 9 條邊。兩者都是同類中最小的非平面圖，它們共同構成了平面性的禁用式。

Euler 不等式有什麼幫助？

平面連通圖的 Euler 公式 V − E + F = 2 結合簡單平面圖的每個面至少有 3 條邊的事實，得出 m ≤ 3n − 6。任何違反此界限的簡單圖立即被判定為非平面。對於二部平面圖，每個面至少有 4 條邊，給出更緊的界限 m ≤ 2n − 4。檢查器將兩者作為快速拒絕規則應用。

大小限制是多少？

檢查器最多可處理 16 個頂點和 60 條邊。這涵蓋了典型的教學和競賽風格圖形，包括 Petersen 圖、Möbius-Kantor 圖、小型超立方體和完全圖 K₇。更大的圖形需要線性時間的專用平面性測試，例如 Hopcroft-Tarjan 或左右平面性測試。

如何繪製證明細分？

當圖形是非平面時，找到的 K₅ 的 5 個分支頂點 —— 或 K₃,₃ 的 6 個分支頂點（分為 A 和 B 兩組）—— 會在內環上突出顯示。10 條（或 9 條）所需的內部頂點不相交路徑各以不同顏色繪製，以便您可以視覺化追蹤 K₅ 或 K₃,₃ 拓撲結構。不屬於細分的頂點和邊會變暗。

延伸閱讀

• 平面圖 — 維基百科
• Kuratowski 定理 — 維基百科
• Euler 示性數 — 維基百科
• Petersen 圖 — 維基百科
• Wagner 定理 — 維基百科