Matchings

Matchings and covers

定义 4.2.1

匹配 (matching): 一个没有自环, 任意两边没有公共端点的图.

浸润的 (saturated): 针对点, 被匹配中的边覆盖的点称为被浸润.

完美匹配 (perfect matching): 所有点都被浸润.

例 4.2.2

$K_{n,n}$ 中的完美匹配共有 $n!$ 种.

$K_{2n}$ 中的完美匹配有 $(2n-1)!!$ 种.

定义 4.2.3

极大匹配 (maximal matching): 无法再增加边的匹配.

最大匹配 (maximum matching): 所有匹配中最大的.

定义 4.2.4

M-交错路径 (M-alternating path): 一条路径, 边交错取.

M-增广路径 (M-augmenting path): 一条交错路径, 但第一个点和最后一个点不被浸润.

定义 4.2.5

$G,H$ 是两个点集为 $V(G)$ 的图.

对称差 (symmetric difference): $G\Delta H$ 表示对两个图的边集去对称差, 点集保持 $V(G)$.

引理 4.2.6

两个匹配的对称差的每一个连通分支要么是一条路径要么是一个偶环.

证明

考虑对称差中每个点的度数不超过 2.

定理 4.2.7 Berge

$M$ 是最大匹配当且仅当 $G$ 中没有 $M$-增广路径.

证明

"$\Rightarrow$": 如果存在增广路, 则匹配可以变大与最大匹配矛盾.

"$\Leftarrow$": 反设不存在增广路径的匹配 $M$ 不是最大匹配, 那么一定存在 $M'$ 更大. 利用引理, 取 $M\Delta M'$, 对于所有偶环, 二者边数相同, 若 $M'$ 更大, 必然存在一条交错路中 $M'$ 边数多, 而该路对于 $M$ 就是增广路径, 与假设矛盾. 故 $M$ 是增广路径.

定义 4.2.8

对于二部图 X,Y 假设 $|X|\leqslant|Y|$.

对任意 $X$ 的子集 $S$ 记 $N(S)=\bigcup\limits_{v\in S}N(v)$.

定理 4.2.9 P.Hall

对于一个二部图 $X,Y$ 含有一个浸润 $X$ 的匹配当且仅当 $|N(S)|\geqslant|S|,\forall S\subseteq X$.

推论 4.2.10

$k$-正则二部图存在完美匹配.

定义 4.2.11

顶点覆盖 (vertex cover): $Q\subset V(G)$, $Q$ 包含每条边至少一个端点, 称 $Q$ 为顶点覆盖.

显然有顶点覆盖大小大于等于匹配大小.

定理 4.2.12 Konig, Egervary

二部图的最大匹配等于最小顶点覆盖.

证明

证明最小的顶点覆盖是最大匹配.

定义 4.2.13

独立数 (independence number): 最大的独立集大小.

边覆盖 (edge cover): 对于任意顶点, 至少与一条边关联.

显然有边覆盖大小大于等于独立数.

注 4.2.14

最小边覆盖是若干个星形图.

定义 4.2.15

- $\alpha(G):$ 最大独立集大小. - $\alpha'(G):$ 最大匹配大小. - $\beta(G):$ 最小顶点覆盖大小. - $\beta'(G):$ 最小边覆盖大小.

引理 4.2.16

$S\subset V(G)$ 是一个独立集, 当且仅当 $\overline{S}:=V(G)-S$ 是一个点覆盖.

因此 $\alpha(G)+\beta(G)=n(G)$.

引理 4.2.17 Gallai

一个没有孤立点的图, 那么有 $\alpha'(G)+\beta'(G)=n(G)$.

证明

"$\beta'(G)\leqslant n(G)-\alpha'(G)$":

考虑取最大匹配, 构造出一个边覆盖不超过右侧.

"$\alpha'(G)\geqslant n(G)-\beta'(G)$":

考虑最小边覆盖, 构造出一个匹配不少于右侧.

注 4.2.18

上述证明过程, 从两个方向分别考虑特殊的'对方', 再利用相应的最大/最小来说明不等号. 注意任意最小边覆盖不一定包含第一步中任取的最大匹配. 所以最大匹配构造的最小边覆盖不一定是整个图的最小边覆盖.

任意最大匹配不一定包含于第二步中选取的最小边覆盖, 所以最小边覆盖中的最大匹配不一定是全图的最大匹配.

定理 4.2.19 Konig, Egervary

没有孤立点的二部图中, 最大独立集大小等于最小边覆盖大小, $\alpha(G)=\beta'(G)$.

4.2 Matchings

Matchings and covers