第十三章：平面圖 — 動畫敘事

第十三集 · Ch.13 平面圖

能不能不交叉？

柯尼斯堡的七座橋，能否各走一次回到起點？
這個 1736 年的謎題，歐拉用一筆畫問題解決了它，
同時奠定了圖論的基礎。
今天我們來看平面圖與歐拉公式。

柯尼斯堡七橋問題

歐拉把這個問題抽象成圖：陸地是節點，橋是邊。
問題變成：能否走過每條邊恰好一次（歐拉路徑）？

歐拉路徑存在的條件

歐拉迴路（回到起點）：所有節點的度數都是偶數
歐拉路徑（不回起點）：恰好有兩個奇數度節點

柯尼斯堡：四個節點度數分別是 3, 3, 3, 5——全是奇數，
所以歐拉迴路不存在！

歐拉公式互動驗證

對任何連通平面圖：V − E + F = 2
（V=頂點數，E=邊數，F=面數，包含外部無限面）

選擇一個圖形驗證

K₅ 和 K₃₃ 不是平面圖

Kuratowski 定理：一個圖是平面圖，若且唯若它不包含 K₅ 或 K₃₃ 的細分。

K₅

5 個頂點完全圖

10 條邊，但平面圖 V=5 時最多 3V-6=9 條邊，所以 K₅ 非平面。

K₃₃

3+3 完全二部圖

9 條邊，但平面二部圖 V=6 時最多 2V-4=8 條邊，所以 K₃₃ 非平面。

V-E+F

歐拉公式推論

連通平面圖：E ≤ 3V-6
連通二部平面圖：E ≤ 2V-4
兩個不等式各自給出上界。

觀念測驗

一個連通平面圖有 8 個頂點、12 條邊，有幾個面（含外部無限面）？

小結

V − E + F = 2

歐拉公式是數學中最優美的等式之一。
不管是三角形、立方體還是任何連通平面圖，
頂點數減邊數加面數，永遠等於 2。

下一集：求和與漸近——大 O 記號的真正含義

1 / 6

本頁為動畫敘事版。看完後可前往完整第十三章進行互動練習。

教材來源：Mathematics for Computer Science (Lehman, Leighton, Meyer)

📚 第十三章：平面圖