第9章 二分圖與匹配

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

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

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

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

9.2 四個例題

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

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

例題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

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