第12章 離散建模與證明

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

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

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

12.2 四個例題

例題1 分派工作用匹配

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

例題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 先，排除了合法安排。應畫無向衝突邊，再用異色表示不同時段。