第十二章：簡單圖 — 動畫敘事
第十二集 · Ch.12 簡單圖
握手定理
聚會上每個人握了幾次手？把所有人的握手次數加起來，
一定是偶數——因為每次握手都貢獻了兩次。
這個直覺就是握手定理，是圖論最基本的事實。
一定是偶數——因為每次握手都貢獻了兩次。
這個直覺就是握手定理，是圖論最基本的事實。
握手定理
握手定理（Handshaking Lemma）
對任意圖 G = (V, E)：
所有頂點的度數之和 = 邊數的兩倍
推論：奇數度的頂點個數一定是偶數個。
Σ deg(v) = 2|E|所有頂點的度數之和 = 邊數的兩倍
推論：奇數度的頂點個數一定是偶數個。
為什麼？每條邊連接兩個頂點，對兩端的度數各貢獻 1。
所以把所有度數加總，每條邊都被數了兩次。
所以把所有度數加總，每條邊都被數了兩次。
互動：建圖並驗證握手定理
點擊兩個節點之間連線（5個節點，自由建圖）
邊數：0 度數和：0 驗證：0 = 2×0 ✓
圖著色 — 四色定理
用最少的顏色為圖的節點著色，讓相鄰節點顏色不同。
地圖上的國家需要幾種顏色？答案是 最多 4 色（四色定理，1976年電腦證明）。
地圖上的國家需要幾種顏色？答案是 最多 4 色（四色定理，1976年電腦證明）。
點擊節點選色，讓相鄰節點顏色不同
特殊圖類
完全圖 Kₙ
每對節點都有邊
邊數 = n(n-1)/2
例：K₄ 有 6 條邊
邊數 = n(n-1)/2
例：K₄ 有 6 條邊
二部圖
節點分兩組，邊只跨組
無奇數環
例：工作-員工匹配
無奇數環
例：工作-員工匹配
正則圖
每個節點度數相同
k-正則：每點度數 k
例：骰子圖（3-正則）
k-正則：每點度數 k
例：骰子圖（3-正則）
樹
連通 + 無環
n 個節點恰好 n-1 條邊
例：家族樹、目錄結構
n 個節點恰好 n-1 條邊
例：家族樹、目錄結構
觀念測驗
一個有 7 個節點的圖，所有節點的度數分別是 1,2,2,3,3,4,5，邊數是多少？
小結
圖論是
萬物互聯的語言
萬物互聯的語言
社群網路、地圖導航、晶片設計——
凡是有「關係」的地方，就有圖論。
握手定理是最簡單的起點，四色定理是最美的定理之一。
凡是有「關係」的地方，就有圖論。
握手定理是最簡單的起點，四色定理是最美的定理之一。
下一集：平面圖——歐拉公式 V-E+F=2
閱讀完整第十二章互動教材 →
1 / 7
本頁為動畫敘事版。看完後可前往 完整第十二章 進行互動練習。
教材來源：Mathematics for Computer Science (Lehman, Leighton, Meyer)