第十三章：平面圖
平面圖是指可以在平面上畫出，且邊與邊之間除了頂點外沒有交叉的圖。這類圖形在電路板設計和地圖繪製中有著重要應用。
13.2 平面圖的定義
平面圖：
若一個圖 G 可以嵌入平面，使得除頂點外，任意兩條邊都不相交，則稱 G 為平面圖。
若一個圖 G 可以嵌入平面，使得除頂點外，任意兩條邊都不相交，則稱 G 為平面圖。
並非所有圖都是平面圖。最著名的兩個非平面圖是 $K_5$（五個頂點的完全圖）和 $K_{3,3}$（三間房子三間公用設施圖）。
13.3 歐拉公式
對於任何連通的平面圖，歐拉公式給出了頂點、邊和面之間的優雅關係：
v - e + f = 2
其中 $v$ 是頂點數，$e$ 是邊數，$f$ 是面數（包括無限大的外部區域）。
🧪 互動：歐拉公式驗證
點擊下方的「面」（區域），計數器會增加。請別忘了點擊最外圈的白色區域！
頂點: 0
邊: 0
面: 0
🧩 挑戰：三間房子三間公用設施 ($K_{3,3}$)
這是一個經典的圖論謎題。你的任務是將三間房子（藍色）分別連接到三間公用設施（橘色：水、電、氣）。
規則： 所有的連線都不能交叉。
房 1
房 2
房 3
水
電
氣
操作：點擊左邊的房子，再點擊右邊的設施進行連線。
13.5 Kuratowski 定理
為什麼 $K_{3,3}$ 這麼難連？Kuratowski 定理告訴我們：
一個圖是平面圖，若且唯若它不包含 $K_5$ 或 $K_{3,3}$ 的細分作為子圖。
這意味著 $K_{3,3}$ 本質上是「非平面」的結構。無論你如何扭曲線條，在平面上一定會產生交叉。
🧪 互動：Euler 公式 V − E + F = 2 即時驗算
調整頂點數和邊數，即時驗算 Euler 公式。（計算式：F = E − V + 2，包含外部無限面）
教材來源：Mathematics for Computer Science (Lehman, Leighton, Meyer)