圖論-L3

L3 匹配與因子

符號定義

符號	意義
$M\subseteq E(G)$	一組匹配(邊集合)
$V(M)$	被 $M$ 中邊覆蓋到的頂點集合
$N(S)$	集合 $S$ 的鄰居集合；Hall 定理中 $S\subseteq X$，$N(S)\subseteq Y$
$o(G)$	$G$ 的奇數階連通分支 (odd components) 個數
$\alpha'(G)$	最大匹配的邊數 (matching number)
$\beta(G)$	最小頂點覆蓋大小
$\alpha(G)$	最大獨立集大小
$\beta'(G)$	最小邊覆蓋大小 (要求沒有孤立點)
$\gamma(G)$	最小支配集大小

---

Matchings and Covers

名詞	定義／判斷方式
Matching (匹配)	一組兩兩沒有共同端點的邊；一個頂點最多被選中的一條邊使用。
Perfect matching (完美匹配)	覆蓋所有頂點的匹配，即 $V(M)=V(G)$。因此頂點總數必為偶數。
$M$-saturated (被 $M$ 飽和)	頂點屬於 $V(M)$，即與 $M$ 中某條邊相接。
$M$-unsaturated (未被 $M$ 飽和／自由頂點)	頂點不屬於 $V(M)$。
Maximal matching (極大匹配)	不能保留既有選邊再多加一條邊的匹配。
Maximum matching (最大匹配)	全圖之中邊數最多的匹配；大小為 $\alpha'(G)$。

• maximum $\Rightarrow$ maximal；maximal 不一定 maximum。
• Perfect matching 若存在，必為 maximum，且 $|M|=n(G)/2$。
• $\#\operatorname{PerfectMatching}(K_{2n})=\frac{(2n)!}{2^n n!}$
  • 排列 $2n$ 個頂點，有 $(2n)!$ 種
  • 每對內部交換不變: 除以 $2^n$
  • $n$ 對交換次序不變: 除以 $n!$

---

• $M$-alternating path ($M$-交錯路徑): 路徑上的邊依序交替「屬於 $M$／不屬於 $M$」。
• $M$-augmenting path ($M$-增廣路徑): 起點、終點都是 $M$-unsaturated 的交錯路徑；首尾兩條邊必不在 $M$，路徑上「非 $M$ 邊」比「$M$ 邊」多一條。
• 沿增廣路徑翻轉:保留路徑外的原匹配邊；路徑內把原本選中的邊移除，把原本未選的邊加入。

---

對稱差: $A\triangle B=(A-B)\cup(B-A)=(A\cup B)-(A\cap B)$

兩個匹配 $M,M'$ 的對稱差構成的非孤立連通分支，只可能是:

• 邊在兩組匹配間交替的路徑，或
• 邊數為偶數的交錯環。

原因:在 $M\triangle M'$ 中，每個頂點至多各接一條來自 $M$、$M'$ 的邊，故度數至多 2；若形成環，兩種邊交替，環長必偶數。

---

Berge 定理 : $M\text{ 是 maximum matching}\iff G\text{ 不存在 }M\text{-augmenting path}$

• 若有增廣路徑，翻轉可讓邊數 $+1$。反之，若存在更大的匹配 $M'$，則 $M\triangle M'$ 中必有一個分支的 $M'$ 邊數比 $M$ 邊數多；該分支即 $M$-增廣路徑。 (講義 P13,20)

Hall’s Matching Condition

Hall 婚姻定理:

對 $(X,Y)$ 二部圖 $G$: $ \exists\text{ 匹配飽和 }X\iff\forall S\subseteq X,\quad |N(S)|\ge |S|$

• $X$ 中任意一組需求者 $S$，它們能連到的候選對象數量不能少於需求者數量。

• 必要性: 若每個 $x\in S$ 都匹配到不同的 $Y$ 頂點，則 $N(S)$ 至少有 $|S|$ 個頂點。

• 充分性反向論證: 若最大匹配 $M$ 未飽和 $X$，取未飽和頂點 $u\in X$；令 $S$ 為從 $u$ 經交錯路徑可達的 $X$ 頂點，$T=N(S)$ 為可達的 $Y$ 頂點。由 Berge 定理無增廣路徑，$T$ 中每個頂點都被 $M$ 配對到 $S-\{u\}$，故 $|N(S)|=|T|=|S|-1<|S|$ ，與 Hall 條件矛盾。 (講義 P26–27)

---

任何 $k\ge1$ 的 $k$-正則二部圖都有 perfect matching。

• $k|X|=|E(G)|=k|Y|\implies |X|=|Y|$
• 任意 $S\subseteq X$，由邊數計算: $k|S|\le k|N(S)|\implies |N(S)|\ge|S|$

因此由 Hall 定理有飽和 $X$ 的匹配，且 $|X|=|Y|$，故為 perfect matching。 (講義 P29)

Min–Max Theorems 與各種覆蓋

名詞	選	需要滿足	最佳化目標／記號
Matching (匹配)	邊	每個點至多被一條選邊使用	最大: $\alpha'(G)$
Vertex cover (頂點覆蓋)	頂點	每一條邊至少一個端點被選到	最小: $\beta(G)$
Independent set (獨立集)	頂點	任意兩個選中點不相鄰	最大: $\alpha(G)$
Edge cover (邊覆蓋)	邊	每一個頂點至少與一條選邊相接	最小: $\beta'(G)$

匹配和頂點覆蓋

對任意 matching $M$ 與任意 vertex cover $S$:

${|M|\le |S|\quad\implies\quad \alpha'(G)\le\beta(G)}$

• 每條匹配邊必至少有一個端點被 $S$ 選中，且不同匹配邊不能共用端點。 (講義 P35-36)

• König–Egerváry 定理: $G\text{ 是二部圖}\implies \alpha'(G)=\beta(G)$

頂點覆蓋與獨立集

$S\text{ 為 vertex cover}\iff V(G)-S\text{ 為 independent set}$

$\alpha(G)+\beta(G)=n(G)$

• 若補集中還有相鄰的兩個頂點，就有一條邊的兩端都未被原集合覆蓋。

邊覆蓋與匹配 (Gallai 定理)

若 $G$ 沒有孤立點 ($\delta(G)\ge1$)，則 $\alpha'(G)+\beta'(G)=n(G)$

證明在講義 P46-49

二部圖且無孤立點的推論:

$\alpha'=\beta,\quad \alpha+\beta=n,\quad \alpha'+\beta'=n \quad\implies\quad \alpha(G)=\beta'(G)$

Maximum Bipartite Matching

Augmenting Path Algorithm (增廣路徑演算法)

1. 給定二部圖 $(X,Y)$ 和目前匹配 $M$；$U=X-V(M)$ 為 $X$ 側未飽和頂點。
2. 初始化 $S=U$、$T=\varnothing$。自 $U$ 開始擴展交錯路徑:從 $X$ 沿非匹配邊到 $Y$，若 $Y$ 頂點已匹配，再沿匹配邊回 $X$；將可達的 $X,Y$ 頂點分別收進 $S,T$。
3. 若抵達未匹配的 $Y$ 頂點，就得到增廣路徑 $P$:更新 $M\leftarrow M\triangle E(P)$，匹配數 $+1$，重新執行。
4. 如果搜尋完仍找不到增廣路徑，按 Berge 得最大匹配，並按 König–Egerváry 得最小頂點覆蓋: $M\text{ maximum},\quad C=(X-S)\cup T\text{ minimum vertex cover}$

範例在講義 P61-82

Matchings in General Graphs

Factor (因子)

名詞	定義
Factor (因子)	原圖的生成子圖: 保留全部頂點，邊可以減少。
$k$-factor ($k$-因子)	每個頂點在該生成子圖中的度皆為 $k$，即 $k$-正則生成子圖。
1-factor	一個 1-正則生成子圖，與 perfect matching 的邊可一一對應。
2-factor	一個 2-正則生成子圖；由涵蓋全部頂點的互不相交環構成。

• perfect matching 是一組邊集合；1-factor 是由該匹配邊構成的生成子圖。

Odd component

• Odd component: 頂點數為奇數的連通分支。
• $o(G)$: 奇數階分支的個數。

對任意 $S\subseteq V(G)$，有奇偶關係 $o(G-S)+|S|\equiv n(G)\pmod2$

• $G-S$ 的偶數階分支貢獻偶數個頂點；奇數階分支的頂點總數與 odd component 個數同奇偶。 (講義 P87)

Tutte 的 1-factor 定理

$G\text{ 有 perfect matching (1-factor)}\iff \forall S\subseteq V(G),\quad o(G-S)\le|S|$

• 刪掉 $S$ 後，每個奇數階分支如果要被原圖中的完美匹配完全覆蓋，都至少有一個頂點必須透過匹配邊連向 $S$；不同奇數分支需要不同的 $S$ 頂點。

範例在講義 P102-103