第十章：有向圖與偏序 — 動畫敘事
第十集 · Ch.10 有向圖與偏序
關係的地圖
課程有先修要求，任務有依賴關係，網頁有超連結——
這些都是有方向性的關係。
有向圖讓我們把這些關係畫成地圖，
再用拓樸排序找出合理的執行順序。
這些都是有方向性的關係。
有向圖讓我們把這些關係畫成地圖，
再用拓樸排序找出合理的執行順序。
DAG — 有向無環圖
課程先修關係：箭頭表示「必須先修」。沒有環路 → 不會出現循環依賴。
● 節點 = 課程
→ 邊 = 先修關係
DAG = Directed Acyclic Graph
可達性矩陣 — 誰能到達誰？
點擊格子可以修改邊，矩陣即時反映傳遞閉包（能否透過多步到達）
綠色 = 可到達（直接或間接） 藍色對角線 = 自己到自己
拓樸排序 — 找合理的學習順序
點擊藍色節點（入度為 0，沒有未完成的先修），依序完成課程：
完成順序：（點選藍色節點開始）
偏序 vs 全序
≤
全序（Total Order）
任意兩個元素都可以比較大小。
例：整數大小、字典序
例：整數大小、字典序
⊆
偏序（Partial Order）
有些元素之間無法比較。
例：集合包含關係、課程先修
例：集合包含關係、課程先修
≡
等價關係
自反 + 對稱 + 遞移。
例：模 n 同餘、同班同學
例：模 n 同餘、同班同學
偏序需要：自反（a≤a）、反對稱（a≤b 且 b≤a → a=b）、遞移（a≤b 且 b≤c → a≤c）
觀念測驗
為什麼課程先修圖必須是 DAG（不能有環）？
小結
1 / 7
本頁為動畫敘事版。看完後可前往 完整第十章 進行互動練習。
教材來源：Mathematics for Computer Science (Lehman, Leighton, Meyer)