# OCME 第10冊 組合與圖論 · v0.2

網站閱讀版 · 繁體中文

![圓形等距共同署名，不分先後。](assets/signature-circle.svg)

本作採非排序共同署名。排列位置不代表先後、地位、貢獻比例或工作分工；未列名不表示不存在，也不表示未曾參與。

出版／營運單位：EVEMISS TECHNOLOGY CO., LTD.

最終權利與授權聲明另行確認，不由署名排版或出版單位名稱代為決定。

# 第1章 計數原理、排列與組合

## 1.1 先說清楚一個結果長什麼樣

計數的第一步是定義一個結果。選兩本書時，{甲,乙} 和 {乙,甲} 是同一組；選正副班長時，(甲,乙) 和 (乙,甲) 是兩個結果。把結果分成互不重疊且涵蓋全部的類別，就可相加。若每個結果恰對應一條兩步選擇路徑，且每個第一步都有相同數目的第二步，就可相乘。第二步數量若因第一步而變，要把各枝的數量相加。

對非負整數 n，n! 是 1 到 n 的乘積。空排列只有一種，所以 0!=1。從 n 個不同物件取 k 個不重複並排序，0≤k≤n，方法數為 P(n,k)=n(n−1)⋯(n−k+1)，其中 k=0 時取空乘積 1。若不計順序，每組恰被算 k! 次，故 C(n,k)=P(n,k)/k!=n!/(k!(n−k)!)。若每格可重用同一批 n 個物件，正長度 k 的序列有 nᵏ 種；長度零只有空序列，無須對 0⁰ 作約定。

![兩個第一步各有三個第二步；從根到葉的路各代表一個結果。](assets/f01-counting-tree.svg)

## 1.2 四個例題

### 例題1 正副有順序，兩人小組沒有

甲、乙、丙三人中選正副班長。正班長有 3 種，副班長只能從剩下 2 人選，故 3×2=6。若只是選兩人小組，每組有 2 種正副安排，故 6÷2=3。

![同一雙人組有兩種正副分配；只選成員時應把它們合成一組。](assets/f02-ordered-versus-unordered.svg)

### 例題2 允許重複與不允許重複

用 0、1、2、3 組成長度 3 的字串，允許開頭是 0。若能重複，每格皆 4 種，得 4³=64；若不能重複，依序只有 4、3、2 種，得 24。

### 例題3 分枝數不同就逐類計

甲櫃有 2 種筆，乙櫃有 3 種筆，兩櫃筆款互不重複。若只在一櫃選一支，按櫃別分成互斥的兩類，總數 2+3=5。若每櫃各選一支，結果由兩個櫃各自的選擇決定，總數 2×3=6。

### 例題4 固定一塊再排列

甲、乙、丙、丁、戊五人排一列，甲乙必相鄰。把甲乙視為一塊，與另三人共四個單位，有 4! 種順序；塊內有甲乙、乙甲兩種。每個合法隊伍能唯一拆回塊順序與塊內順序，所以共 2·4!=48。

## 1.3 練習

1. **B10-C01-Q01** 用五個不同字母排兩格，不重複，幾種？
2. **B10-C01-Q02** 從五人選兩位不分職務，幾種？
3. **B10-C01-Q03** 從 1、2、3 中組成長度 4 的序列，允許重複，幾種？
4. **B10-C01-Q04** 1、2、3、4 四個數字組成四位數且不重複，末位須偶數，幾種？
5. **B10-C01-Q05** 從七人選三位，指定的甲一定入選，幾種？
6. **B10-C01-Q06** 六件不同禮物送給甲、乙各一件，不重複，幾種？
7. **B10-C01-Q07** 在八本書中選零本或八本，各有幾種？
8. **B10-C01-Q08** 五個不同物件排一列，指定甲不可在第一格，幾種？
9. **B10-C01-Q09** 若從五人選兩人可重複，但不計次序，能用 5²÷2 嗎？
10. **B10-C01-Q10** 證明 C(n,k)=C(n,n−k)，條件 0≤k≤n。

## 1.4 完整解答

### Q01

第一格 5 種，第二格剩 4 種。每個有序對只由一條選擇路徑生成，所以 5×4=20。

### Q02

先算有序 5×4，再除以同一雙的 2 種順序，得 10。

### Q03

每個位置有 3 種且不影響其他位置，故 3⁴=81。

### Q04

末位先取 2 或 4，共 2 種。餘下 3 個位置放其餘 3 個數，各用一次，共 3!；得 2·3!=12。

### Q05

甲已固定，還須從其餘六人選兩位，不分順序，所以 C(6,2)=15。

### Q06

甲先選 6 種，乙剩 5 種，故 30。即使禮物不排序，收件人不同，所以不除以 2。

### Q07

選零本只有空集合，選八本只有全體，所以 C(8,0)=C(8,8)=1。

### Q08

第一格由另外 4 個選，剩四個物件任排，有 4!。總數 4·24=96；也等於 5!−4!。

### Q09

不能：同一人取兩次只有一種順序，兩人不同才有兩種。分開算 5 種重複與 C(5,2)=10 種不同，共 15。

### Q10

把每個 k 元子集對應到它的補集，補集恰有 n−k 個元素。取兩次補集回到原集合，故是一一且滿的對應，兩數相等。


# 第2章 二項式與鴿籠原理

## 2.1 係數數選法，鴿籠找保證

對非負整數 n，展開 (x+y)ⁿ 時從每個因子選一項。得到 xⁿ⁻ᵏyᵏ，正好要在 n 個因子中選 k 個取 y，所以係數是 C(n,k)。當 1≤k≤n−1，依最後一個因子取 x 或 y 分類，得到 C(n,k)=C(n−1,k)+C(n−1,k−1)。兩端係數為 1，n=0 時只有常數項 1。代 x=y=1 得每列係數和為 2ⁿ。

設 m、k 為正整數，每個物件恰放入 m 個箱之一。若各箱至多 k−1 個，總數至多 m(k−1)；所以 N>m(k−1) 就保證某箱至少 k 個。對 N≥1，取 k=⌈N/m⌉ 可知某箱至少有這麼多。若各箱可自由放入 k−1 個，平均放 m(k−1) 個時每箱恰有 k−1 個，說明再少一個就無法保證。若另有分箱限制，需依實際限制找未達標的配置。

![內部係數由左上和右上相加；每列兩端都等於 1。](assets/f03-pascal-triangle.svg)

## 2.2 四個例題

### 例題1 第十三個才保證

13 張卡各入四個箱。若每箱至多 3 張，合計至多 12 張，矛盾。所以某箱至少 4 張。12 張可採每箱 3 張，故 13 是最小保證門檻。

![四個箱各放三個仍未出現四個同箱；第 13 個物件必使某箱達到四個。](assets/f04-pigeonhole-threshold.svg)

### 例題2 展開時只找想要的一項

(x+2y)⁵ 的 x³y² 項，從五因子選兩個給 2y。係數 C(5,2)·2²=10·4=40；另三個 x 不改係數。

### 例題3 一列係數可用一個代入加總

(1+t)⁶ 的係數依次是 1、6、15、20、15、6、1。代 t=1 即得到總和 2⁶=64，不必逐項加算。

### 例題4 把餘數當箱子

任取七個整數，按除以 6 的餘數 0 到 5 分箱。七個物件進六箱，有兩個同餘；兩數之差被 6 整除。若只有六個，0 到 5 各一個就不能保證。

## 2.3 練習

1. **B10-C02-Q01** 求 (1+t)⁴ 的 t² 係數。
2. **B10-C02-Q02** 求 (x−2)⁴ 的 x² 係數。
3. **B10-C02-Q03** 用前一列的兩個係數算 C(7,3)。
4. **B10-C02-Q04** (1+t)⁵ 的所有奇次係數之和？
5. **B10-C02-Q05** 22 本書各放入五格。無論如何分配，最滿的一格至少有幾本？請給出達到這個最小值的分法。
6. **B10-C02-Q06** 三種顏色的球，至少抽幾顆才保證有三顆同色？假設各色供應充分。
7. **B10-C02-Q07** 從 13 人的出生月份，能保證什麼？
8. **B10-C02-Q08** 若 16 個物件入四箱，必有一箱至少五個嗎？
9. **B10-C02-Q09** 證明 n≥1 時，(x+y)ⁿ 兩端係數都是 1。
10. **B10-C02-Q10** 五種標籤各最多重複使用兩次。若已標 11 件會怎樣？

## 2.4 完整解答

### Q01

四個因子中選兩個取 t，其餘取 1，係數 C(4,2)=6。

### Q02

選兩個因子取 −2，另兩個取 x。乘上 (−2)²，係數 C(4,2)·4=24。

### Q03

分指定元素是否入選，得 C(6,2)+C(6,3)=15+20=35。兩類沒有重疊。

### Q04

把 t=1 與 t=−1 的值相減，偶次抵消、奇次變兩倍。故奇次和為 (32−0)/2=16。

### Q05

每格至多 4 本時只有 20 本，所以至少一格 5 本。分成 5、5、4、4、4 可達，不能保證有 6 本。

### Q06

未達標時，每色可至多兩顆，合計 6 顆；6 顆可每色兩顆。故至少 7 顆才保證。

### Q07

按 12 個月份分箱。若每月最多一人，總共最多 12 人，所以至少兩人同月，不必同日。

### Q08

不必。每箱 4 個就合計 16，且沒有五個同箱。要保證至少 5 個，最小是 17 個。

### Q09

xⁿ 只能從每個因子取 x，yⁿ 只能從每個因子取 y；兩個選擇各只有一種。若 n=0，只有常數項 1，不是兩項。

### Q10

每種若最多用兩次，最多能標 5·2=10 件。標了 11 件代表原限制無法同時滿足，至少一種標籤用到三次。


# 第3章 容斥原理

## 3.1 把每個物件的淨次數算成一

對有限集合 A、B，|A∪B|=|A|+|B|−|A∩B|：兩邊都屬於的物件先被計兩次，再扣一次。三集合時先加單集合、減兩兩交集、再加三重交集，因同在三集合的元素先加 3、減 3，必再補 1。

對 m 個集合，對每個非空索引子集 J，把其交集大小乘 (−1)^(|J|−1) 加起來。若某元素恰在 r 個集合，淨次數為 C(r,1)−C(r,2)+⋯+(−1)^(r−1)C(r,r)=1，理由是二項式 (1−1)ʳ=0（r≥1）。r=0 時沒有任何項。若題目要「一個條件都不碰」，先在明定的全集計數，再扣聯集；若要「恰中一個」，三重交集的係數又不一樣。

![在兩個集合都出現的物件，要從加法總數扣一次，才只算一遍。](assets/f05-union-count.svg)

## 3.2 四個例題

### 例題1 倍數聯集要扣最小公倍數

在 1 到 30，3 的倍數有 10 個，5 的倍數有 6 個；同時是兩者倍數等於是 15 的倍數，有 2 個。故至少符合一個有 10+6−2=14 個，兩者都不符合有 30−14=16 個。

![從 1 到 30，3 或 5 的倍數分別有 10、6 個，兩者的共同倍數有 2 個。](assets/f06-multiples-ledger.svg)

### 例題2 三集合的共同部分加回

某班以 A、B、C 記三項活動，單集合人數 12、11、9，兩兩交集人數依 AB、AC、BC 為 5、4、3，三重交集 2。至少參加一項為 12+11+9−5−4−3+2=22。若全班 30 人，三項皆未參加有 8 人。

### 例題3 分辨恰好一項與至少一項

沿用例題2，恰好一項用單集合和減兩倍兩兩交集和，再加三倍三重交集。淨次數對參與 1、2、3 項分別是 1、0、0，所以為 32−2·12+3·2=14。

### 例題4 用補集計禁位排列

把三封不同的信放入三個不同信封，每個信封恰放一封。問沒有信放入對應信封的方式數。全部有 3!=6 種。用容斥，至少一封放對有 3·2!−3·1!+0!=4 種。固定一封後兩封任排；固定兩封後最後一封也被迫放對；固定三封只剩一種。故全錯有 6−4=2 種。

## 3.3 練習

1. **B10-C03-Q01** 40 人中 A 有 18 人，B 有 15 人，兩者都有 7 人，至少一者多少？
2. **B10-C03-Q02** 1 到 24，能被 4 或 6 整除的個數？
3. **B10-C03-Q03** 1 到 20，不是 2 也不是 5 的倍數有幾個？
4. **B10-C03-Q04** 三集合大小各 8，兩兩交集大小各 3，三重交集大小 1，聯集多少？
5. **B10-C03-Q05** 沿用上一題，恰好屬於兩集合的元素有幾個？
6. **B10-C03-Q06** A⊆B 時，容斥公式為何只剩 |B|？
7. **B10-C03-Q07** 若兩集合沒有交集，可直接加嗎？
8. **B10-C03-Q08** 把四封不同的信放入四個不同信封，每個信封恰放一封。沒有信放入對應信封的方式有幾種？
9. **B10-C03-Q09** 三集合中，某元素恰在 A、C，三集合公式對它計幾次？
10. **B10-C03-Q10** 1 到 30 中 3 或 5 的倍數，恰好只中其中一條有幾個？

## 3.4 完整解答

### Q01

聯集為 18+15−7=26 人。其餘 14 人兩者皆無。

### Q02

各有 6、4；共同倍數是 12 的倍數，有 2。故 6+4−2=8。

### Q03

聯集 10+4−2=12，從全集 20 扣除，剩 8。

### Q04

依次加、減、加，得 3·8−3·3+1=16。

### Q05

兩兩交集的總數為 9，其中每個三重交集元素計三次。要留下恰兩者的元素，扣 3·1 得 6。

### Q06

交集就是 A，因此右側 |A|+|B|−|A|=|B|；左側聯集也就是 B。

### Q07

可以；每個物件只在其所在集合被計一次。這是交集修正項為零的情形。

### Q08

全部 4!=24。至少一封對用容斥：4·3!−6·2!+4·1!−0!=24−12+4−1=15；全錯 24−15=9。

### Q09

單集合加兩次，兩兩交集只有 AC 扣一次，沒有三重交集項，所以淨計 1 次。

### Q10

先算兩個集合人數和 16；共同的 2 個在和中各計兩次，要全部扣掉，共 16−4=12。


# 第4章 遞迴、生成函數與Catalan數

## 4.1 先有初值，再比較生成函數的係數

遞迴關係說明後項如何由前項決定；還要給足初值。例如 aₙ=aₙ₋₁+aₙ₋₂ 適用於 n≥2，a₀、a₁ 一旦給定，就能依序算出全部。公式相同但初值不同，答案可以不同。

本冊用實變數 t 的解析普通生成函數 A(t)=Σ aₙtⁿ，其中 n 從 0 起算。先找 R>0，使級數在 |t|<R 絕對收斂。兩個級數都絕對收斂時，乘積的雙重和也絕對收斂，因為絕對值總和是 (Σ |aᵢtⁱ|)(Σ |bⱼtʲ|)。可按總冪次重排，故 tⁿ 的係數是 Σ aᵢbₙ₋ᵢ（0≤i≤n）。兩個冪級數若在原點附近相等，由冪級數的逐項微分，係數等於各階原點導數除以階乘。

合法括號字串有 n 個左括號與 n 個右括號，每個前綴的左括號不少於右括號。令 Cₙ 為其數量，空字串給 C₀=1。非空字串可寫成 (U)V，第一個使高度回到零的右括號，恰好結束外層括號。回零之前高度至少為 1，所以去掉外層後，U 的相對高度非負並回到零；V 從零開始，亦合法。反過來，兩個合法字串 U、V 接成 (U)V 時，外層的右括號就是首次回零。因此 Cₙ=Σ CᵢCₙ₋₁₋ᵢ（0≤i<n）。

至多有 2^(2n)=4ⁿ 個長度 2n 的括號字串，因此 C(t)=Σ Cₙtⁿ 在 |t|<1/4 絕對收斂，Cauchy 乘積給 C(t)=1+tC(t)²。Cₙ 是 Catalan 數，與二項係數 C(n,k) 的記號有別。

把左、右括號分別當作上升、下降一步。n≥1 時有 C(2n,n) 條回零路徑。不合法者先到高度 −1；把截至首次 −1 的步子上下對換。此前高度皆非負，反射後此前皆非正，而該點成了首次到 1。後續步子不動，故終點升到 2。

反過來，任何終點為 2 的路徑必先到高度 1；反射截至首次 1 的步子，會回到終點 0，且在對應點首次到 −1。兩次反射翻同一段，因此互為逆。終點為 2 的路徑有 n+1 次上升、n−1 次下降，共 C(2n,n+1) 條。相減並約分得 Cₙ=C(2n,n)/(n+1)；n=0 時此式亦給 1。

![左括號升一格、右括號降一格；合法路徑回到零，途中不跌到零以下。](assets/f07-catalan-prefix-path.svg)

## 4.2 四個例題

### 例題1 三對括號的五種來自哪裡

C₁=C₀C₀=1，C₂=C₀C₁+C₁C₀=2。C₃ 依內部 0、1、2 對分類，為 1·2+1·1+2·1=5。分類由第一個配對右括號決定，不重不漏。

![三對括號按第一對括號內部有幾對分三類；各類數量是 2、1、2。](assets/f08-recurrence-catalan-split.svg)

### 例題2 幾何級數的係數是等比數列

a₀=1、aₙ=2aₙ₋₁，得 aₙ=2ⁿ。當 |t|<1/2，A(t)=Σ(2t)ⁿ 絕對收斂。把 2tA(t) 從 A(t) 扣掉只剩 1，因此 A(t)=1/(1−2t)；t=1/2 不能由此宣布收斂。

### 例題3 從兩個初值推出生成函數

取 a₀=0、a₁=1，n≥2 時 aₙ=aₙ₋₁+aₙ₋₂。由初值及遞迴歸納得 0≤aₙ≤2ⁿ，故 |t|<1/2 可移項。把 n≥2 的遞迴乘上 tⁿ 加總：aₙ₋₁ 的和是 t(A(t)−a₀)，aₙ₋₂ 的和是 t²A(t)。因此 A(t)−t=tA(t)+t²A(t)，得 A(t)=t/(1−t−t²)。依遞迴前六項為 0、1、1、2、3、5。

### 例題4 Catalan 的兩個根只留一個

由 C=1+tC²，整理得 (1−2tC(t))²=1−4t。冪級數使 1−2tC(t) 在 |t|<1/4 連續，且在 t=0 等於 1。右側在這個實區間內嚴格為正，所以左側平方裡的量無法穿過零，必取正根。由此對 t≠0 得 C(t)=(1−√(1−4t))/(2t)=2/(1+√(1−4t))。後一式在 t=0 也等於 1。

## 4.3 練習

1. **B10-C04-Q01** a₀=2，aₙ=aₙ₋₁+3，求 a₁ 到 a₄。
2. **B10-C04-Q02** a₀=1，aₙ=3aₙ₋₁，求 a₃ 及 A(t)。
3. **B10-C04-Q03** 求 (1+t+t²)(1+2t) 的 t² 係數。
4. **B10-C04-Q04** 沿用例題3求 a₆、a₇。
5. **B10-C04-Q05** 用 Catalan 遞迴算 C₄。
6. **B10-C04-Q06** 「())(」左右括號一樣多，是合法括號字串嗎？
7. **B10-C04-Q07** 「(()())」的 (U)V 分解是什麼？
8. **B10-C04-Q08** 對例題3的二階遞迴，只知道 a₀=0，為何還不能決定所有項？
9. **B10-C04-Q09** aₙ=n! 的普通生成函數有原點附近正的收斂半徑嗎？
10. **B10-C04-Q10** 為何 C(t)=1+tC(t)² 中有一個 t？

## 4.4 完整解答

### Q01

逐次加 3，得 5、8、11、14。由每步差固定可寫 aₙ=2+3n。

### Q02

逐次乘 3 得 a₃=27。係數是 3ⁿ，在 |t|<1/3 可用幾何級數得 A(t)=1/(1−3t)。

### Q03

冪次 2 來自 t²·1 或 t·2t，前者 1、後者 2，合計 3。

### Q04

a₆=a₅+a₄=5+3=8，a₇=a₆+a₅=8+5=13。

### Q05

按 i=0、1、2、3，依序有 1·5、1·2、2·1、5·1，總數 14。

### Q06

不是。前三個字元「())」已有 1 個左與 2 個右，前綴高度為 −1。最後回到零不能補救。

### Q07

首次回零在最後一格，外面第一、末字元為一對，U=「()()」、V 為空字串。U 的兩對屬於外層內部。

### Q08

a₁ 尚可自由選。比如 a₀=0，取 a₁=0 得全零；取 a₁=1 得 a₂=1，之後也不同。需要兩個初值。

### Q09

沒有。任意 t≠0，級數項絕對值的相鄰比為 (n+1)|t|，終會大於 2，所以項不趨 0。形式符號可以記係數，但不能按本章當成解析函數。

### Q10

配對的外層括號本身占一對。C² 中 t^(n−1) 給 U、V 共 n−1 對；乘 t 把這個係數放到 n 對。常數 1 對應空字串。


# 第5章 圖、walk、path與連通

## 5.1 圖由頂點和邊決定，不由畫法決定

本冊先用有限簡單無向圖 G=(V,E)。一條邊是兩個不同頂點組成的無序對；沒有自環，也不把同一對重複計為兩邊。畫在紙上的線若相交，只有交點被明確指定為頂點時才算接通。頂點的度數 deg(v) 是接到它的邊數；每條邊貢獻兩個端點，故所有度數和是 2|E|。

walk（遊走）是至少含一個頂點的序列，每相鄰兩項都要有邊，長度是步數，頂點與邊可以重複。頂點全不重複的 walk 稱簡單道路；只停在一個頂點是長度零的道路。若 walk 兩次到同一頂點，可剪去兩次之間的閉段。步數每次減少，最後得到同端點的道路。簡單環是至少三步的封閉 walk，起終點相同，其餘頂點互不重複且與起點不同。

能以道路相連的頂點構成連通關係：長度零保證自己連自己，反走保證對稱，接兩條再剪除重複保證傳遞。因此頂點分成互不相交的連通分量，孤立頂點各自成一分量。

![圖的連通分量由能否沿邊到達決定；沒有任何邊的 F 仍是一個頂點與一個分量。](assets/f09-graph-components.svg)

## 5.2 四個例題

### 例題1 剪去中途折返

令頂點 A、B、C、D，邊 AB、BC、BD。A,B,C,B,D 每步有邊，是長度 4 的 walk，重訪 B 也重用 BC，故不是道路。剪去 B,C,B 的閉段，保留一次 B，得到 A,B,D，長度 2。

![A→B→C→B→D 是四步遊走；剪去 B→C→B，剩 A→B→D 的道路。](assets/f10-walk-versus-path.svg)

### 例題2 從邊表找全部分量

頂點 A 到 F，邊 AB、BC、DE。從 A 可達 B、C，不能到 D、E；D 和 E 互通；F 沒有邊。分量依次是 {A,B,C}、{D,E}、{F}，共三個。

### 例題3 度數和核對邊數

頂點 A 到 D，邊 AB、AC、BC、CD。度數分別是 2、2、3、1，總和 8，所以邊數 4。反過來，若抄到度數和 7，這張無向圖的抄表必有錯。

### 例題4 找不到路，也要給理由

在例題2，若 A 到 E 有道路，途中必第一次離開 {A,B,C}。但邊表中沒有跨出此集合的邊，所以不存在。只列幾條失敗的路不足以證明不連通。

## 5.3 練習

1. **B10-C05-Q01** 頂點 A、B、C，邊 AB、BC。A,C 是 walk 嗎？
2. **B10-C05-Q02** 同圖，A,B,A 是 walk 或道路？
3. **B10-C05-Q03** 在 A、B、C 上沒有邊。分量數與度數和？
4. **B10-C05-Q04** A 到 D，邊 AB、AC、AD。求各點度數。
5. **B10-C05-Q05** 某簡單無向圖有 7 條邊，度數和多少？
6. **B10-C05-Q06** 在例題2加邊 CE，列出新分量。
7. **B10-C05-Q07** 一條道路有 6 個頂點，長度幾步？
8. **B10-C05-Q08** 圖畫上 AB 和 CD 交叉但沒標交點，A 能走到 D 嗎？若沒有其他邊。
9. **B10-C05-Q09** 一張簡單無向圖若有兩個頂點度數為奇數，能斷定它連通嗎？
10. **B10-C05-Q10** 為何同一頂點到自身允許長度零道路？

## 5.4 完整解答

### Q01

不是。這是一步序列，需要 AC；兩步 A,B,C 才合法。

### Q02

是 walk，因無向的 AB 可反向走。它重訪 A，也重用 AB，所以不是道路。

### Q03

三點互相不可達，每點各一分量，度數和 0。

### Q04

A 接到三條，其他三點各接一條，所以是 3、1、1、1，總和 6。

### Q05

每邊的兩端各加一，故 2·7=14。

### Q06

CE 把原來的 ABC 和 DE 連起來，F 仍無邊。新分量是 ABCDE 與 F。

### Q07

相鄰頂點間各一步，6 個頂點有 5 個間隔，所以長度 5。

### Q08

不能。邊只有兩個各自的端點對；交叉不新增頂點或邊，因此分量 AB 和 CD 分開。

### Q09

不能。只含 AB 這一條邊，再加孤立頂點 C，度數為 1、1、0，仍有兩分量。

### Q10

序列只含該點，沒有相鄰兩項需要檢查，且不重複頂點。這也讓孤立點與自己連通。


# 第6章 樹與生成樹

## 6.1 樹保留可達性，不保留多餘的環

樹是頂點非空、連通且無簡單環的有限簡單無向圖。連通給任兩點至少一條道路。若有兩條不同道路連接同一對端點，沿共同開頭走到第一次分岔，接著沿其中一條走到第一次再遇上另一條。這一段和另一條道路的對應段只在兩端相接，因此形成環。反過來，在非空圖中，若任兩點間恰有一條道路，圖必連通；若有環，環上相鄰兩點可由該邊或沿環的另一側相連，矛盾。

一棵至少兩點的樹必有度數為 1 的葉：取一條最長道路，端點若還有別的鄰點，鄰點不在道路上就可延長，在道路上則形成環。刪葉與它的唯一邊後仍連通無環，因其他兩點間的道路不可能經葉當中繼。以單點 0 條邊起算，歸納得 n 點樹有 n−1 條邊。

非空連通圖若有環，刪掉其中一邊。任何原本用到該邊的道路，都可改走環的其餘邊，得到同端點的 walk，再剪掉重複點成道路。因此刪邊後仍連通。有限次刪除後得到保留全部頂點的連通無環子圖，這就是生成樹。故非空連通的 n 點圖至少有 n−1 條邊；若恰有 n−1 條，原圖已是樹。無環圖有 c 個分量時，每個分量是一棵樹，合計 n−c 條邊。

![樹上 A 到 E 的道路只有一條；C 的葉支不會成為繞行替代路。](assets/f11-tree-unique-path.svg)

## 6.2 四個例題

### 例題1 環上刪一邊不會斷開

圖 A 到 D 的邊為 AB、BC、AC、CD。刪 AC，還有 A→B→C；剩 AB、BC、CD 連成四點道路，沒有環且含全部頂點，是一棵生成樹。

![左圖含三角環，刪去 AC 後保留全部頂點與連通，得到右圖的生成樹。](assets/f12-spanning-tree-delete.svg)

### 例題2 只數 n−1 不足以判樹

在 A 到 D 上取 AB、BC、AC，邊數為 4−1，但前三點成環，D 孤立。對非空的 n 點圖，若已知連通，n−1 條邊即保證是樹；若已知無環，由 n−c=n−1 得 c=1，也可推出是樹。

### 例題3 森林可從分量讀邊數

頂點 A 到 G，邊 AB、BC、DE、DF。分量 ABC、DEF、G 都無環；邊數分別 2、2、0，合計 4=7−3。孤立點也是一棵單點樹。

### 例題4 生成樹不一定唯一

三角形 AB、BC、AC，任刪一邊都留下三點道路，故有三棵生成樹。原圖的環邊是選項，不是要保留的必要邊。

## 6.3 練習

1. **B10-C06-Q01** 單點、零邊的圖是樹嗎？該點是葉嗎？
2. **B10-C06-Q02** 七點樹的邊數及度數和？
3. **B10-C06-Q03** A 到 E，邊 AB、AC、AD、DE。列出葉。
4. **B10-C06-Q04** 在上一題，B 到 E 的唯一道路？
5. **B10-C06-Q05** 五點連通簡單圖有四條邊，必是樹嗎？
6. **B10-C06-Q06** 五點無環圖有兩個連通分量，幾條邊？
7. **B10-C06-Q07** 四邊形 AB、BC、CD、AD，刪 BC 後仍連通嗎？
8. **B10-C06-Q08** 四點圖只有 AB、CD，是否有生成樹？
9. **B10-C06-Q09** 從至少兩點的樹刪去任一邊，還能連通嗎？
10. **B10-C06-Q10** 若是 n≥2 點的道路圖，有幾個葉？

## 6.4 完整解答

### Q01

是樹：非空、自身可達、無環。該點度數是 0，本冊定義葉為度數 1，因此不是葉。

### Q02

樹有 7−1=6 邊，每邊兩端，度數和 12。

### Q03

A 度 3、D 度 2；B、C、E 度 1，因此葉是 B、C、E。

### Q04

先從 B 到其唯一鄰點 A，再沿 AD、DE，為 B,A,D,E。樹性排除任何另一條道路。

### Q05

是。若有環，刪一邊仍連通，只剩三邊，違反連通的五點圖至少四邊。

### Q06

每個分量是樹，分量內點數各減一再加，等於 5−2=3。

### Q07

是，B,A,D,C 是涵蓋四個頂點的道路，所以剩下是連通的三邊樹。

### Q08

無。選子集合只會刪邊，不會創造跨分量的邊；保留全點的子圖不可能連通。

### Q09

不能；若兩端仍有道路，加回被刪的邊便形成一個環，違反樹的無環性。

### Q10

首尾各接一條邊，其餘點各接前後兩條。故只有兩端是葉；例如五點道路的葉是 A、E。


# 第7章 圖同構與不變量

## 7.1 先用不變量排除，再用雙射確認

圖同構是頂點的雙射 f，使任何不同 u、v 都滿足：uv 是原圖的邊，若且唯若 f(u)f(v) 是另一圖的邊。雙射保證頂點不重不漏，「若且唯若」保證邊與非邊都被保留。給了完整邊表時，可逐邊映射並比對得到的邊集合是否恰等於目標邊集合。

改標號或重新畫圖不改圖本身的關係。頂點數、邊數、度數的多重集合、各分量大小、有無三角形，都是同構不變量：例如 f 把 v 的鄰點一一送到 f(v) 的鄰點，故度數相等。只要一項不同，就能否證同構；相同的幾項通常不能證明同構。小圖可用度數縮小候選，最後以雙射與邊集核對。

![重新排列圖上的位置不改邊集；三條邊在兩張圖之間逐一對應。](assets/f13-isomorphism-redraw.svg)

## 7.2 四個例題

### 例題1 相同度數，不同分量

六點環 AB、BC、CD、DE、EF、AF 與兩三角形 AB、BC、AC、DE、EF、DF，都有六點六邊且每點度數 2。前者連通，後者分兩塊；同構保留可達性，所以不同構。

![六點大環和兩個三角形的每點度數都是 2，但連通分量數不同。](assets/f14-same-degrees-different-graphs.svg)

### 例題2 用雙射交出可核對的證明

G 的邊 AB、BC、CD，H 的邊 AC、AD、BD。取 f(A)=C、f(B)=A、f(C)=D、f(D)=B；映到的邊依次是 AC、AD、BD，恰好整個 H。四個像不同，故為同構。

### 例題3 一看度數就可否證

四點道路的度數排序是 1、1、2、2；四點星形為 1、1、1、3。有度 3 頂點只在後者，故不用遍歷雙射。

### 例題4 少檢查非邊會誤判

三點道路 AB、BC 到三角形 AB、BC、AC，恆等映射把原圖每條邊送到邊，但原非邊 AC 成為邊。雖然頂點雙射，仍不是同構。

## 7.3 練習

1. **B10-C07-Q01** 三角形三頂點重新命名後，會和原圖同構嗎？
2. **B10-C07-Q02** 比較四點圖 AB、BC、CD 與 AC、CD、BD 是否同構。
3. **B10-C07-Q03** 三點道路和三點空圖是否可能同構？
4. **B10-C07-Q04** 兩張四點圖邊數同為 2。一張 AB、BC，另一張 AB、CD。同構嗎？
5. **B10-C07-Q05** 若同構 f 將 A 送到 X，且 A 孤立，X 必孤立嗎？
6. **B10-C07-Q06** 四點環的度數排序？
7. **B10-C07-Q07** 五點道路與三角形加一條分離邊，邊數相同嗎？是否同構？
8. **B10-C07-Q08** 六環和兩個三角形的度數相同，數出各自三角形數。
9. **B10-C07-Q09** 例題2 的映射把非邊 AC 送成什麼？
10. **B10-C07-Q10** 兩張同為連通、同點數且同邊數的圖，必同構嗎？

## 7.4 完整解答

### Q01

會。任一頂點重新命名的雙射都把三個無序點對一一送到三個無序點對；兩圖都是全有邊。

### Q02

都是四點道路。依序把第一圖的 A,B,C,D 送到第二圖的 A,C,D,B，邊像為 AC、CD、BD，恰是全邊。

### Q03

不可能。前者 2 邊，後者 0 邊；同構會一一對應所有邊。

### Q04

前者含一個度 2 頂點和一個孤立點；後者每點度數 1。度數多重集合不同，所以否。

### Q05

必然。若 X 有鄰點 Y，由雙射可取 Y 的原像 v，且 v≠A。因 f(A)f(v)=XY 是邊，由同構的逆向條件，Av 必為原圖的邊，與 A 孤立矛盾。

### Q06

每個頂點各接環的前後一邊，故排序仍為 2、2、2、2。

### Q07

兩者皆 4 邊；道路只有一個分量，另一張有三點和兩點兩個分量，所以不同構。

### Q08

六環中每點只有前後兩個鄰點，而這兩個鄰點彼此不相鄰。若有三角形，取其中任一點，另外兩點就必須是它彼此相鄰的鄰點，矛盾。所以六環有 0 個三角形；另一圖每個分量各有 1 個，共 2 個。

### Q09

原像 A→C、C→D，故送到 CD，而 H 的邊只有 AC、AD、BD；CD 不是邊。

### Q10

不必。四點星形與四點道路都連通且有三邊，但星形的最大度是 3，道路的最大度是 2。


# 第8章 Euler路徑與迴路

## 8.1 每條邊恰一次，頂點可以重訪

trail（跡）是每步有邊且沒有重複用邊的 walk；可以多次走到同一頂點。Euler 跡用完圖的每條邊恰一次，若起終點相同稱 Euler 迴路。本章的「Euler 路徑」指這種跡，不要求頂點互異；它也不是走遍每個頂點恰一次的問題。

一條 Euler 跡經過中途頂點時，每次進、出配成一對。若起終點不同，兩端各多一次未配對，故正好兩個奇度頂點；若封閉，全部為偶度。所有有邊的頂點還必須在同一分量，因一路走不過互不相連的邊塊。孤立點不影響。頂點非空而無邊時，可停在任一頂點，視為長度零的迴路；空頂點圖不在此約定內。

若圖至少有一條邊、有邊部分連通且全偶度，從任一有邊頂點沿未用邊走到不能再走。若停在非起點，該點用過的邊數為奇數，原度數為偶數，所以仍有未用邊，矛盾。故先得封閉跡。若仍有未用邊，從封閉跡上一點走到某條未用邊的端點，再接上該邊。這段 walk 的第一條未用邊，其出發點已在封閉跡上。扣掉原跡後，各點剩餘度數仍為偶數，於此走出另一封閉跡並插回。每次至少多用一邊，有限次後用完。

若正好兩個奇度點且有邊部分連通，暫加一條連接兩點的專用邊，使所有度數為偶數。即使已有同端點的邊，也把專用邊視為不同一條。前面的度數配對與插接按邊身分進行，仍適用。把所得封閉跡旋轉到以專用邊為第一步，刪去這一步，餘下即為原圖的 Euler 跡。

![一個三角形接一段尾巴，奇度點為 C、D；若要把每條邊走一次，端點必是 C 與 D。](assets/f15-euler-odd-endpoints.svg)

## 8.2 四個例題

### 例題1 用插接把兩圈接起來

邊為 AB、BC、AC、CD、DE、CE。A,B,C,A 是第一圈。當它走到 C 時插入 C,D,E,C，得 A,B,C,D,E,C,A。C 重訪，但六條邊各用一次，所以是 Euler 迴路。

![兩個三角形在 C 相接；先走一圈，回到 C 時可插入另一圈，邊不重複。](assets/f16-euler-splice.svg)

### 例題2 兩奇點要做兩端

邊為 AB、BC、AC、CD。A、B 度 2，C 度 3，D 度 1。可從 D 走 D,C,A,B,C，恰用四邊。因起終點不同，這是一條 Euler 跡而非迴路。

### 例題3 全偶還可能走不完

兩個不相連的三角形，每點度數皆 2，但從第一塊不可能跨到第二塊。有邊頂點不在同一分量，所以沒有 Euler 跡或迴路。

### 例題4 孤立點不改邊走訪

頂點 A、B、C、D，前三點成三角形，D 孤立。A,B,C,A 仍用完全部邊，D 不需要訪問。若四點都孤立，停在 A 即可用完零條邊。

## 8.3 練習

1. **B10-C08-Q01** A 到 E，邊 AB、BC、CD、DE。Euler 跡端點？
2. **B10-C08-Q02** 四點星形 AB、AC、AD 有 Euler 跡嗎？
3. **B10-C08-Q03** 三角形 A,B,C,A,B 是 trail 嗎？
4. **B10-C08-Q04** 四環 AB、BC、CD、AD 給一條 Euler 迴路。
5. **B10-C08-Q05** 在上題四環加 AC，應從哪兩點之一出發？
6. **B10-C08-Q06** 有兩塊各只有一條邊 AB、CD，會有 Euler 跡嗎？
7. **B10-C08-Q07** 若 Euler 迴路沿途到達同一頂點兩次，會違反定義嗎？
8. **B10-C08-Q08** 頂點 A、B 但無邊，寫一條 Euler 迴路。
9. **B10-C08-Q09** 若某點度數為 1，能有 Euler 迴路嗎？
10. **B10-C08-Q10** 三角形接 CD 的例題，A,C,D,B 是 Euler 跡嗎？

## 8.4 完整解答

### Q01

A、E 度 1，其餘度 2，有邊部分連通。A,B,C,D,E 恰用完，端點 A、E；不能閉合。

### Q02

A 度 3，B、C、D 各 1，有四個奇度點，超出最多兩端，所以沒有。

### Q03

不是。第一步與最後一步都是同一條無向邊 AB，雖然每步都有邊，也不符合不重用。

### Q04

A,B,C,D,A 順著環走，四條邊依序 AB、BC、CD、DA，最後回到 A。

### Q05

新增邊使 A、C 度數從 2 變 3，只有它們是奇點。可走 A,B,C,D,A,C，從 A 到 C，反向也合法。

### Q06

沒有。兩個有邊分量無法相互到達；也有四個奇度點。任一理由都足以排除。

### Q07

不會。Euler 條件限制的是邊各一次，不限制頂點；例題1在 C 匯合兩圈就是合法的。

### Q08

序列 (B) 不走任何邊，起終點都是 B；圖中沒有邊漏掉。

### Q09

不能。封閉跡在每個點使用的入與出必成對；該點唯一的邊無法成對，所以不可能用完後閉合。

### Q10

不是，D 到 B 需要 DB，但圖沒有這條邊；也沒用完四條。先逐步檢查鄰接，再檢查用邊清單。


# 第9章 二分圖與匹配

## 9.1 配對先查端點，最優還要找界

二分圖把頂點分成不相交且覆蓋全部的 L、R 兩部，每條邊跨部。空部與孤立點皆可。沿環走時兩部交替，故二分圖沒有奇環。反過來，每個分量任取根，按最短距離奇偶分部。若某邊兩端同奇偶，從根走到第一端、跨該邊，再沿第二端的路回根，長度為兩個距離之和加 1，是奇數。若這個封閉 walk 有額外重複點，可在兩次到同一點處切成兩段較短的封閉 walk；總長奇數，所以一段仍奇。重複切短到只剩首尾重複，便得到奇環。無奇環時，所有邊因此都跨部。

匹配是沒有共用端點的邊集合。極大匹配（maximal）不能直接再加一邊；最大匹配（maximum）是所有匹配中邊數最多；完美匹配覆蓋每個頂點。最大一定極大，反向不成立。一個二分圖的匹配最多用 min(|L|,|R|) 條邊，因每邊各占兩部一點。

對既定匹配，增廣路是至少有一邊的簡單道路，兩端未配對，沿路的邊交替未選、已選，首末皆未選。翻轉選邊時，拿掉路上已選邊、加入路上未選邊。內點各換掉一條匹配邊，兩端各添一條配對；未選邊比已選邊多一條，所以新匹配大小恰加一。找到增廣路便證原匹配尚非最大；在本章小圖中，可用匹配上界或列盡候選核對最大值。

![左部 A、C 與右部 B、D；每條邊都跨部，孤立頂點可放任一部。](assets/f17-bipartite-sides.svg)

## 9.2 四個例題

### 例題1 不能再加，卻仍能換得更多

四點道路 AB、BC、CD。匹配 {BC} 已極大，因兩條剩邊都碰到 B 或 C；但沿 A,B,C,D 翻轉，把 BC 換為 AB、CD，得大小 2。四點每邊占兩點，大小 2 已是最大且完美。

![原本只選 BC；沿 A→B→C→D 翻轉選邊狀態，得到不共端點的 AB、CD。](assets/f18-matching-augment.svg)

### 例題2 列出二分並驗全部邊

四環 AB、BC、CD、AD 可分 {A,C} 與 {B,D}。四條邊都跨部，因此二分。三角形不行：A、B 必異部，C 鄰 B 被迫與 A 同部，卻又鄰 A。

### 例題3 每部容量可給最優上界

頂點 A 到 E，部 {A,B} 與 {C,D,E}，邊 AC、AD、BD、BE。匹配 {AC,BE} 有兩條；左部只有兩點，不可能有第三條，所以最大為 2。這個匹配留下 D 未配。

### 例題4 兩部一樣大仍可能不完美

部 {A,B,C} 與 {D,E,F}，邊 AD、BD、CE、CF。A 和 B 只可用同一個 D，不能同時都配上。可取 AD、CE 達到兩條；三條會配滿左部，已排除。因此最大為 2。

## 9.3 練習

1. **B10-C09-Q01** AB、AC 能一起選入匹配嗎？
2. **B10-C09-Q02** 四點星形 AB、AC、AD 的最大匹配大小？
3. **B10-C09-Q03** 在四環 AB、BC、CD、AD，列一組完美匹配。
4. **B10-C09-Q04** 五點道路 AB、BC、CD、DE 是否有完美匹配？
5. **B10-C09-Q05** 只含兩條分離邊 AB、CD 的圖，空匹配是極大嗎？
6. **B10-C09-Q06** 六點環可二分嗎？
7. **B10-C09-Q07** 五點環 AB、BC、CD、DE、AE 能二分嗎？
8. **B10-C09-Q08** 在道路 A,B,C,D,E，已有 {BC,DE}。它已達最大嗎？
9. **B10-C09-Q09** A 到 D，邊 AB、BC、CD。從 {BC} 增廣後，哪兩點由未配變已配？
10. **B10-C09-Q10** 為何增廣路內部的頂點不會在翻轉後同時配兩邊？

## 9.4 完整解答

### Q01

不能，兩邊共享端點 A。匹配先查邊存在，再逐一查端點是否重複。

### Q02

任兩邊都共用 A，所以至多一條；任取 AB 達到一條。

### Q03

取 AB、CD，邊均存在且端點分別為 A、B、C、D，四點全部恰配一次。

### Q04

不能。每條匹配邊占兩點，覆蓋點數為偶數，不會等於 5；但 {AB,CD} 可配四點。

### Q05

不是。可加入 AB 而不碰已配點；空匹配合法，但只要圖有邊就不是極大。

### Q06

令環沿 A,B,C,D,E,F,A，交替分部 {A,C,E} 與 {B,D,F}；最後 FA 也跨部。

### Q07

不能。兩部交替走五步會換到另一部，但最後應回到原點同一部，矛盾。

### Q08

兩條邊互不共端點。五點最多配 ⌊5/2⌋=2 條，故它已達最大，但不是完美。

### Q09

翻轉後有 AB、CD，A、D 原先未配而現在各配一次；B、C 由原互配改為與兩端配。

### Q10

內點沿路恰有一條已選、一條未選。因原邊集合是匹配，該內點已配在路上，不會另有路外的匹配邊。翻轉移除前者，加入後者，因此該內點仍只配一次。


# 第10章 著色、Clique與頂點覆蓋

## 10.1 上界要有做法，下界要有理由

正常頂點著色給每個頂點一種顏色，且每條邊的兩端異色。最少所需顏色數稱 χ(G)。Clique（團）是任兩個不同頂點皆相鄰的頂點集，最大大小記 ω(G)。團內顏色全不同，故 χ≥ω。給出合法 k 色配置，只推出 χ≤k；要證恰需 k 色，還須證任何至多 k−1 色的配置都不合法。空頂點圖約定 χ=0；非空無邊圖只需一色。

頂點覆蓋 C 要求每條邊至少一端在 C。補集 S 是獨立集，因為其中任兩點若相鄰，就有一條邊未被 C 覆蓋。反過來，獨立集的補集會覆蓋每條邊。|C|=|V|−|S|，因此最大獨立集大小為 α(G) 時，最小頂點覆蓋大小 τ(G)=|V|−α(G)。一組覆蓋給 τ 的上界；有 k 邊的匹配則給 τ≥k，因為每條匹配邊都需選到一端，而且這些端點互不相同。

「極小覆蓋」是刪掉任何點就不再覆蓋，「最小覆蓋」比較所有覆蓋的大小；同理，不能擴張的團未必是最大的團。小圖可用具體配置和相等的上下界，也可逐一排除更小候選。

![同一個四環可兩色著色、最大團有兩點、最小覆蓋也有兩點；三個任務檢查不同條件。](assets/f19-color-clique-cover.svg)

## 10.2 四個例題

### 例題1 五環的色數高於最大團

五環 AB、BC、CD、DE、AE 沒有三角形，最大團大小 2。若只兩色，沿 A,B,C,D,E 交替使 A、E 同色，違反 AE。改用 A,C 第一色、B,D 第二色、E 第三色，合法，故 χ=3>ω=2。

![五環沿邊兩色交替會使首尾衝突；用第三色可修正，因此恰需三色。](assets/f20-odd-cycle-color-bound.svg)

### 例題2 四環的三個不同最優值

四環 A,B,C,D,A 可把 {A,C} 與 {B,D} 著兩色；一條邊阻止一色，故 χ=2。沒有三角形且有邊，故 ω=2。{A,C} 覆蓋全邊，而匹配 {AB,CD} 逼至少兩點，所以 τ=2。

### 例題3 不能刪點的覆蓋仍可能太大

星形 AB、AC、AD。{B,C,D} 覆蓋所有邊，少任一葉就漏該邊，故極小；但只取中心 {A} 也覆蓋，最小大小為 1。

### 例題4 貪婪著色依賴頂點順序

四點道路 A,B,C,D，按 A、D、B、C 順序每次取可用最小色。A、D 得色 1；B 鄰 A 得 2；C 鄰 B、D 已有 2、1，只能得 3。換成按道路順序就可兩色；貪婪一次不是最優證明。

## 10.3 練習

1. **B10-C10-Q01** 三角形的 χ、ω 各是多少？
2. **B10-C10-Q02** 三角形最少幾個點才覆蓋所有邊？
3. **B10-C10-Q03** 只有 AB、CD 兩條分離邊時，一點能覆蓋全部嗎？
4. **B10-C10-Q04** 五點道路 A,B,C,D,E，給最大獨立集並證明大小。
5. **B10-C10-Q05** 上題最小頂點覆蓋大小？
6. **B10-C10-Q06** 四點無邊圖的 χ、ω、τ？
7. **B10-C10-Q07** 若找到合法四色配置，能宣布色數等於 4 嗎？
8. **B10-C10-Q08** 若一個圖含四點團，能宣布全圖剛好需要四色嗎？
9. **B10-C10-Q09** 若覆蓋 C 再加入一個頂點，還是覆蓋嗎？
10. **B10-C10-Q10** 星形的葉 B、C 是否都要取才能形成大小 2 的團？

## 10.4 完整解答

### Q01

任兩點相鄰，三點成團，故 ω=3 且至少三色；每點各一色可行，故 χ=3。

### Q02

選一點只碰兩邊，另外一邊漏掉；任選兩點皆可，所以最小大小 2。

### Q03

不能，一點只會屬於其中一條邊。取 A、C 達到兩點，最少就是 2。

### Q04

取 {A,C,E}，任兩點不相鄰。有兩條不交邊 AB、CD，每條至多取一端，再加 E，至多 3 點，所以達最大。

### Q05

{A,C,E} 的補集 {B,D} 覆蓋。由最大獨立集大小 3，最小覆蓋為 5−3=2。

### Q06

所有點可同色；單點成團但兩點不成團；空集合已覆蓋零條邊。因此依次是 1、1、0。

### Q07

不能，只能說 χ≤4。四點道路的四個頂點各用一色也合法，但它可以兩色著色。若要證色數為 4，還須證至多三色無法合法配置。

### Q08

只能說至少四色。全圖其他邊可能逼更多色，例如五點完全圖含四點團卻需要五色。

### Q09

是。原來每條邊已至少有一端在 C，加入頂點不會移除原有端點。若加入的是 C 原先未含的頂點，集合大小增加 1。

### Q10

不是。B、C 互不相鄰，兩葉不能成團；取中心 A 和任一葉才有一條邊，形成大小 2 的團。


# 第11章 有向圖與拓撲排序

## 11.1 箭頭代表必須先發生的條件

有限簡單有向圖的一條邊是有序對 (u,v)，記 u→v，且 u≠v。不放自環或同向重邊，但 u→v 與 v→u 可同時存在，這會構成長度 2 的有向環。入度數指有多少箭頭進入該點，出度指有多少箭頭離開；入度和與出度和都等於邊數。

拓撲排序列出所有頂點各一次，並讓每條 u→v 的 u 早於 v。有向環會迫使某點早於自己，故不能排序。無有向環的有向圖稱 DAG。若有限非空圖沒有入度 0 的點，從任一點反覆選一個前驅，必有第一次重訪。把兩次出現同一點之間的片段倒過來讀，就沿箭頭形成一個有向環。因此非空 DAG 至少有一個入度 0 的點。

Kahn 方法每次選一個目前入度 0 的點，放到排序的下一格，再刪該點與其出邊。若原圖無環，剩圖仍無環，故總能繼續到取完；每個點被取出時，原先指向它的前驅都已取出。空頂點圖的排序是空序列。若剩圖非空卻無入度 0 的點，前驅論證給出一個環。檢查單一排序提案時，須先核對頂點各一次，再逐邊核對順序。某個提案失敗時，仍可用上述程序檢查是否存在其他排序。

![A 必須先於 B、C，兩者都必須先於 D；B 與 C 可交換。](assets/f21-dag-choices.svg)

## 11.2 四個例題

### 例題1 同一張 DAG 可以有兩個答案

箭頭 A→B、A→C、B→D、C→D。初始只有 A 入度零；刪 A 後 B、C 都可選；D 等它們都取出才可選。因此合法排序恰為 ABCD 與 ACBD。

![A,B,C,D 與 A,C,B,D 都合法；B,A,C,D 違反 A→B。](assets/f22-topological-order-check.svg)

### 例題2 循環依賴不能排順序

箭頭 A→B、B→C、C→A。若有排序，必有 A 在 B 前、B 在 C 前、C 在 A 前，矛盾。三點各入度 1，演算法起步就停。

### 例題3 有向走法不能借用反向

有 A→B、B→C，從 A 可以沿箭頭到 C；從 C 沒有出邊，不能反走到 A。A 的入度／出度為 0／1，B 為 1／1，C 為 1／0。

### 例題4 沒有依賴的點可以插入多處

若三點只有 A→B，C 與其他無關。保留 A 在 B 前，把 C 放前、放中或放後，得到 CAB、ACB、ABC。只有一條邊不意味一定只有一個排序。

## 11.3 練習

1. **B10-C11-Q01** 三點只有 A→B、B→C，有幾種拓撲排序？
2. **B10-C11-Q02** 例題1的 ACDB 合法嗎？
3. **B10-C11-Q03** 三點無邊，拓撲排序有幾個？
4. **B10-C11-Q04** A→B 和 B→A 是同一條邊嗎？可拓撲排序嗎？
5. **B10-C11-Q05** A→C、B→C、C→D，初始可選哪些？
6. **B10-C11-Q06** 四點有向圖的總入度 5，總出度多少？
7. **B10-C11-Q07** 序列 ABA 對只有 A→B 的兩點圖能當拓撲排序嗎？
8. **B10-C11-Q08** 剩三個頂點，每個目前入度皆正；為什麼可判有向環？
9. **B10-C11-Q09** 若 A→B、B→C，能否加 C→A 而維持 DAG？
10. **B10-C11-Q10** 若 A→B、B→C，加入 A→C 會移除某個原合法排序嗎？

## 11.4 完整解答

### Q01

A 必在 B 前，B 必在 C 前；三點都須出現，唯一是 ABC。

### Q02

不合法。雖然 A 在 B、C 前，D 卻在 B 前，違反 B→D；將 B 移到 D 前即可成 ACBD。

### Q03

所有排列都沒有邊約束，故有 3!=6 種。

### Q04

不同。它們一前一後各要求相反的先後，形成兩點環，不存在排序。

### Q05

A、B 沒有入邊，可任選其一；C 有兩條入邊，D 有一條，兩者都不能先取。

### Q06

每條邊恰有一個出發端和一個到達端，故兩種總和都等於邊數 5。

### Q07

不能。A 重複，序列不是所有頂點各一次；即使某次 A 在 B 前也不夠。

### Q08

從剩圖任一點出發，反覆取一個剩圖中的前驅。因每點目前入度皆正，每步都能取到。剩圖有限，直到第一次遇到已見的點為止，把兩次遇見該點之間的片段反向讀，就得到沿箭頭的環。

### Q09

不能。新增邊閉合 A→B→C→A 這個環，拓撲排序不可能。

### Q10

不會。原來已強迫 A 在 B 前且 B 在 C 前，故 A 已在 C 前。新邊不新增有效限制。


# 第12章 離散建模與證明

## 12.1 把每條限制對到模型裡的一個條件

從題目先抄下「什麼是一個結果」與「哪一種結果不合格」。若結果是按人分派、不得共用對象，頂點可表示人與物，允許配對為邊；若限制是兩活動不能同時，畫無向衝突邊，顏色是時段；若限制是先後，畫有向邊。三者的邊語意不同，不能只因都畫成圖就用同一算法。

正確性要走兩個方向：任何合法安排都能化成模型中的候選；任何通過模型檢查的候選也能還原成合法安排。若要用模型數方案，須證明候選與合法安排一一對應。例如時段有名稱時，顏色也要綁定時段名稱。若求最優，先給可行配置，再證明不存在更好的配置。

![看限制屬於不共用、不同時或先後，再選匹配、著色或拓撲排序。](assets/f23-model-selection.svg)

## 12.2 四個例題

### 例題1 分派工作用匹配

A、B、C 是三個角色，D、E、F 是三個名額。允許邊 AD、AE、BE、CE、CF；每個名額至多一人。選 AD、BE、CF，三邊都在清單且端點不共用，三人全配。反向看，任何完整分派的三個人名額對都是匹配，故模型沒有放鬆限制。

![左側為三個角色、右側為三個名額；所選三條允許邊無共端點，故給一組完整分派。](assets/f24-assignment-certificate.svg)

### 例題2 排衝突時段用著色

活動 A、B、C 互相衝突，D 只與 C 衝突。任一合法時段安排是正常著色，因每條邊兩端不可同時。前三個活動形成三角形，逼至少三個時段；把 D 排在 A 時段，其餘 B、C 各一個，所有衝突均避開，故三個足夠。

### 例題3 先後限制不能用無向圖代替

有 A→C、B→C、C→D。A、B 可互換，但兩者都先於 C，C 先於 D。ABCD、BACD 是全部順序；若把箭頭抹去，只能知道有衝突或相連，讀不出先後。

### 例題4 同一個計數用兩種方法互驗

n 人各和其他人握手一次。以無序對計得 C(n,2)；以端點計，n 人各算 n−1 次，總和 n(n−1)，每次握手被兩人各數一次，除 2 得同值。取 n=6 得 15 次。

## 12.3 練習

1. **B10-C12-Q01** 四人互相握手一次，共幾次？
2. **B10-C12-Q02** 任務 A、B、C，名額 D、E。若允許所有配對，可以三人都分到不同名額嗎？
3. **B10-C12-Q03** 只有衝突 AB、BC、CD，最少需幾個時段？給安排。
4. **B10-C12-Q04** 只有 A、B、C 三項工作，先後限制為 A→B、A→C。C 能否最先？列出所有合法順序。
5. **B10-C12-Q05** 把可雙向通行的走廊視為邊。若要每條恰走一次，應用頂點著色還是 Euler 跡？
6. **B10-C12-Q06** 從四名代表選兩位，再從選出的兩位指定一人發言。有幾種安排？應用組合數還是排列數？
7. **B10-C12-Q07** 兩份名單各 9、8 人，重複 3 人。若活動只邀每人一次，有幾人？
8. **B10-C12-Q08** 圖中有三條兩兩不共端點的邊，有人宣稱兩點已覆蓋全部。如何否證？
9. **B10-C12-Q09** 六點圖有五邊，有人認定為樹。用一個小圖反駁。
10. **B10-C12-Q10** 若文字規則是 A 與 B 不可同時，有人畫 A→B。這個模型錯在哪裡？

## 12.4 完整解答

### Q01

每次是不同的無序雙人組，C(4,2)=6；也可算 4·3 再除以 2。

### Q02

不行。每個合法配對占一個名額，只有兩個名額。可配 AD、BE 兩人，所以最大是 2。

### Q03

邊 AB 使一個時段不足；把 A、C 放第一，B、D 放第二，三邊都異時，所以恰需兩個時段。

### Q04

C 的前驅是 A，不能最先。A 先做後 B、C 可互換，所以 ABC、ACB 都合法，且沒有第三種。

### Q05

把走廊的交會點或末端當頂點，每條走廊當一條無向邊。要使各邊恰好走一次，應用 Euler 跡：先查所有有邊頂點是否同一分量，再查奇度點。若指定起終點，還要核對它們是否符合端點條件。

### Q06

結果分發言與非發言角色，應用有序選擇。先選發言者 4 種，再選另一位 3 種，共 12；也可先選雙人組再選一人發言。

### Q07

名單聯集才是人數。重複者已被算兩次，扣一次，得 9+8−3=14。

### Q08

每個頂點至多碰這三條邊中的一條；兩點最多照顧兩條，至少一條邊沒端點被選。所以宣稱不可能。

### Q09

令 AB、BC、AC 成三角形，D、E、F 上只有 DE、EF。共有五邊卻分兩塊，且含環；這反例符合數量，不符合樹。

### Q10

原規則也允許 B 先於 A；箭頭 A→B 卻只允許 A 先，排除了合法安排。應畫無向衝突邊，再用異色表示不同時段。