目錄
這是 Stanford CS103 導讀的第 11 篇，對應 Spring 2026 官方 Lecture 9（2026-04-20）。課程團隊是 Cynthia Bailey Lee 與 Alex Aiken；公開頁面沒有逐堂標示實際講者，因此本文不猜講者。講次頁面與完整投影片公開，錄影與逐字稿只在 Canvas／Panopto，本文沒有使用。
本講的官方題目是 Graphs, Part I。課程從「一群物件及其關係」抽象出圖，再用兩個配置問題引出頂點覆蓋與獨立集。最後的核心是一個 iff 定理：集合 C 是頂點覆蓋，恰好在它的補集 V − C 是獨立集時成立。
圖把領域故事壓縮成關係結構
公路地圖、化學鍵、社交關係看來分屬不同領域，卻共享同一骨架：有一批物件，以及物件之間的連結。圖論刻意捨去物件的材質與連結的物理意義，只保留「誰和誰相連」。這不是不在乎現實，而是選擇眼前推理真正會用到的資訊。
一張圖包含節點（node，亦稱 vertex）與邊（edge，投影片也提到 arc）。圓點與線段只是表示法；數學物件本身不是那張圖片。頂點可以是城市、分子、單字或工作，邊可代表道路、化學鍵、一步轉換或衝突。只要推理只依賴連結方式，同一定義便能跨領域使用。
抽象前仍要固定語意：哪些東西算頂點？什麼條件才放一條邊？若把「認識」與「互相信任」都含糊叫作連結，所得圖未必能回答精確問題。形式化不替你決定語意；它迫使你先決定語意，再讓集合語言接手。
無向圖與有向圖的形式定義
無向圖寫成有序對 G = (V, E)。V 是頂點集合；E 是邊集合，每條邊是取自 V 的兩元素無序集合 {u, v}。因集合沒有順序，{u, v} = {v, u}，所以邊沒有偏好的起點與終點。能雙向通行的道路常可如此建模。
有向圖（directed graph 或 digraph）也寫成 G = (V, E)，差別是每條邊為頂點的有序對 (u, v)。此時 (u, v) 與 (v, u) 一般不同，可表示網頁從 u 指向 v、帳號 u 追蹤 v，或狀態 u 能一步轉到 v。方向是邊的一部分，不只是畫上的箭頭。
不要混淆兩層順序。外層 G = (V, E) 必須是有序對，否則分不出頂點集與邊集；內層的無向邊 {u, v} 卻是無序集合。讀形式定義時，逐層確認括號代表 ordered pair 還是 set，一個符號差異就會改變合法輸入。
合法性檢查比看圖猜答案可靠
判斷 G = (V, E) 是否為無向圖，可逐條檢查：每個邊元素是否真由兩個相異頂點組成？兩端是否都屬於 V？是否把 (u, v) 當成無向邊？是否把單一頂點或三元素集合放進 E？畫面像網路不代表集合表示合法。
有向圖的邊則必須是 V × V 中的有序對。頂點本身幾乎可以是任何物件，但邊不能指向 V 外。這種 type-checking 習慣會延伸到後面的自動機：先確認物件符合定義，再討論它的性質。
同一張圖可重新排列頂點、把邊畫成曲線，甚至讓線段在平面交叉；只要 V、E 不變，數學結構就沒變。交叉處若未列為頂點，就不是新頂點。證明必須依集合與量詞，不能依版面位置。
Self-loop 揭示兩種邊的差異
從頂點連回自己的邊稱為 self-loop。依本講的無向圖定義，一條邊是含兩個相異元素的集合 {a, b}；{v, v} 會塌成單元素集合 {v}，不合定義。所以無向圖一般不允許 self-loop；這是定義的結果，不是額外背誦的規則。
有向邊是有序對，(v, v) 仍是 V × V 的合法元素，所以有向圖通常允許 self-loop，除非題目另有限制。這個例子訓練我們從資料型態讀出後果，而不是看到兩種圖都能畫圈就宣稱都合法。
投影片另訂慣例：若未特別說明，graph 指 undirected graph。題目只寫 graph 時，不應偷偷加入方向；需要方向會寫 directed graph 或 digraph。固定這項慣例，後面的 edge、cover、adjacent 才不會出現兩套解讀。
頂點覆蓋：每條邊至少選一端
第一個動機是森林步道上的巡護員：要在路口配置人員，使步道上的健行者能看到某一端的人員。抽象後，要求變成「每條邊至少有一個端點被選中」。對 G = (V, E)，頂點覆蓋是 C ⊆ V，且
∀u ∈ V. ∀v ∈ V. ({u, v} ∈ E → (u ∈ C ∨ v ∈ C)).關鍵是析取 ∨：至少一端在 C，兩端都在也可以。它不要求恰好選一端，也不要求每個頂點被選。孤立頂點沒有 incident edge，不選它不會破壞條件；C = V 永遠是 cover，只是不一定小。
implication 也很重要。對任意 u, v，只有 {u, v} ∈ E 時才產生義務；不是邊的配對讓前件為假。檢查候選 C 時，最直接就是掃過 E，確認沒有一條邊的兩端都落在 V − C。
獨立集：選到的頂點彼此不相鄰
第二個動機是為加州神鷲設置巢位：若兩個候選位置彼此可見，就不能同時使用。要選一組頂點，使任兩個被選頂點之間都沒有邊。I ⊆ V 是獨立集，若
∀x ∈ I. ∀y ∈ I. {x, y} ∉ E.獨立不表示頂點與整張圖隔絕。x ∈ I 可以連向許多 V − I 中的頂點；禁止的只是 I 內部出現邊。空集合與任何單元素集合自然獨立，因為不存在兩個被選且相鄰的頂點。「是獨立集」和「是最大獨立集」也是兩回事。
檢查候選集合可逐一檢查 I 內所有頂點對，或掃描所有邊，確認沒有一條邊兩端同時在 I。第二種說法已和頂點覆蓋的失敗條件十分接近，補集關係因此浮現。
補集把兩個配置問題接在一起
定理是：令 G = (V, E) 為圖，C ⊆ V。則 C 是 G 的頂點覆蓋，若且唯若 V − C 是 G 的獨立集。
把頂點分成 C 與外面的 V − C。若 C 覆蓋每條邊，就不可能有一條邊的兩端都在外面，所以外面沒有內部邊。反過來，若外面彼此不相鄰，每條邊便不可能兩端都在外面，故至少一端在 C。
不過 iff 不能只靠圖像直覺。正式證明要有兩個方向。投影片把第一方向寫成直接 lemma，另一方向則證逆否命題。這個安排同時複習全稱量詞、存在量詞、否定、任意選取與 witness。
第一方向：頂點覆蓋推出補集獨立
假設 C 是頂點覆蓋，要證明 V − C 是獨立集。任取 x, y ∈ V − C，目標是 {x, y} ∉ E。因為它們在補集，所以 x ∉ C 且 y ∉ C。
反設 {x, y} ∈ E。既然 C 是頂點覆蓋，這條邊至少一端在 C，所以 x ∈ C ∨ y ∈ C，與 x ∉ C ∧ y ∉ C 矛盾。故 {x, y} ∉ E。由於 x, y 任意，補集內任兩點都不相鄰，V − C 是獨立集。
變數的引入順序很重要。C 是 cover 是已知的全稱敘述，不能因此隨意挑邊；它等到有候選邊時才實例化。目標也是全稱敘述，所以先請讀者任選 x, y。把 assume/prove 兩欄展開，便看得出該引入的是目標中的 x, y，不是重新宣告 G, C。
第二方向：用逆否命題找出反例邊
要證「若 V − C 獨立，則 C 是 cover」，投影片改證逆否：若 C 不是 cover，則 V − C 不是獨立集。這個版本讓否定產生的 witness 直接成為答案。
cover 的否定不是「有頂點沒被選」，而是存在一條未覆蓋的邊：有 x, y ∈ V，使 {x, y} ∈ E、x ∉ C、y ∉ C。因此 x, y ∈ V − C，而同一條 {x, y} 又在 E，補集裡便有兩個相鄰頂點，所以不是獨立集。
這次假設是存在量化，應立即取出其見證 x, y；目標「不是獨立集」也需要一對相鄰的補集頂點，使用相同見證即可。證明沒有創造物件，只把假設給的反例邊搬到目標需要的位置。
否定定義是第二方向的核心
將 cover 定義逐步否定，可避免靠語感出錯：
¬∀u ∈ V. ∀v ∈ V. ({u,v} ∈ E → (u ∈ C ∨ v ∈ C))
≡ ∃u ∈ V. ∃v ∈ V. ({u,v} ∈ E ∧ u ∉ C ∧ v ∉ C).全稱變存在，implication 的否定由 ¬(P → Q) 變成 P ∧ ¬Q，再用 De Morgan 定律否定析取。所得不是抽象的「沒覆蓋好」，而是可操作證據：一條邊與兩個都不在 C 的端點。
獨立集定義的否定則是「存在 I 中兩個頂點，其間有邊」。兩個否定式其實描述同一種壞情況，只是集合名稱不同。能把自然語言壓成精確否定，通常就已找到證明骨架。
Iff 為什麼由兩個 lemma 組成
令 A 表示「C 為 cover」，B 表示「V − C 獨立」。第一個 lemma 證 A → B。第二個證 ¬A → ¬B，它正是 B → A 的逆否命題，兩者合起來覆蓋 iff 的兩個方向。
常見錯誤是把第一方向換句話證兩次，卻沒從補集獨立推出 cover。草稿頂端寫下 A → B 與 B → A，能快速核對完整性；若改證逆否，也要標明替代哪個方向。
示意圖只能建立直覺，不能取代一般證明。定理量化所有圖與所有 C ⊆ V；形式論證必須任取圖和集合，再由定義推出結論，才能涵蓋不同大小與形狀。
大獨立集與小頂點覆蓋是同一選擇
找到獨立集 I，補集 V − I 就是 cover；找到 cover C，補集就是獨立集。有限圖中 |I| + |C| = |V|。因此讓 I 盡量大，等價於讓互補的 C 盡量小。
注意 large 與 largest、small 與 smallest 的差別。任何獨立集都對應 cover，但只有最大獨立集的補集才是最小 cover。再也塞不進頂點的 maximal independent set，也未必是全域 maximum。這些詞不是定理前提，卻是理解演算法問題的必要界線。
投影片把有效率地找 maximum IS 或 minimum VC 連到後面的複雜度理論，以多項式時間 O(n^k) 表達「有效率」。此處重點不是解公開難題，而是理解結構定理如何轉換任務：解出一邊，取補集就得到另一邊。
一個可執行的小例子
令 V = {a,b,c,d}，E = {{a,b},{b,c},{c,d}}。取 C = {b,c}，每條邊至少碰到 b 或 c，所以是 cover。其補集 {a,d} 內沒有邊，所以獨立。
若取 C = {b}，邊 {c,d} 兩端都不在 C，所以它不是 cover。補集 {a,c,d} 確實含 {c,d}，故不獨立。這條失敗邊同時充當兩個否定命題的 witness，重現第二個 lemma 的邏輯。
反向練習：取 I = {a,c}。因 {a,c} 不在 E，它獨立；補集 {b,d} 會覆蓋三條邊。不要只畫圈判斷，請逐條邊寫出至少一端在 cover，或逐對驗證獨立集內沒有邊。
常見誤區與自我檢查
第一，把 edge cover 與 vertex cover 混淆。本講的 C 由頂點組成，任務是碰到每條邊。第二，把 independent set 說成「頂點沒有任何邊」；它只禁止集合內部的邊。第三，忘記 iff 的另一方向，或未說明逆否替代哪一方向。
第四，否定 cover 時只寫 u ∉ C ∨ v ∉ C。一條邊只要一端在 C 就已覆蓋，真正反例要求兩端都不在，即 u ∉ C ∧ v ∉ C。第五，看到 {u,v} 就當 ordered pair；無向邊是集合，交換順序不產生新邊。
可用四問自檢：V 與 E 的元素型態是什麼？候選集合是 V 的子集嗎？目標定義展開後有哪些量詞？主張失敗時，最小 witness 是頂點、邊，還是一對集合？回答完再證明，比追著圖形走穩定。
材料缺口與閱讀界線
公開投影片支持本文的形式定義、兩個應用故事、補集定理及兩個 lemma。它也有期中考行政資訊與即時投票；本文只保留理解圖論所需的內容，沒有把特定日期的考試安排寫成現行建議。
錄影、逐字稿與課堂討論未公開，因此不重建講者的口頭比喻、學生回答或 deck 未載明的推導。paths、trails、local area networks 與 trees 是下一講主題，本文不提前展開。
更新紀錄
- 2026-08-22：依 Graphs, Part I 官方投影片重建全文，補齊形式定義、補集 iff 定理與兩個方向的證明。
參考資料
Loading...