5.8.4 匹配

1. 匹配

图 $G$ 的边集 $M$ 称为 $G$ 中的一个匹配,当且仅当 $M$ 不含环,并且 $M$ 的任何两条不同的边都没有公共端点.

$G$ 的匹配 $M^{\ast }$ 称作饱和匹配,如果 $G$ 中不存在匹配 $M$ 使得 $M^{\ast }\subset M.G$ 的匹配 $M^{\ast \ast }$ 称作极大匹配,如果 $G$ 中不存在匹配 $M$ 使得 $\left|M\right|>\left|M^{\ast \ast }\right|$ .

如果 $G$ 的匹配 $M$ 使得 $G$ 的每个顶点都是 $M$ 的一条边的端点,那么 $M$ 称为完全匹配.

• 在图 5.55 中 $M_1=\{\{2,3\},\{5,6\}\}$ 是饱和匹配,而 $M_2=\{\{1,2\},\{3,4\},\{5,6\}\}$ 是极大匹配, 并且也是完全匹配.

2. 塔特 (Tutte) 定理

设 $q\left(G-S\right)$ 表示 $G-S$ 的具有奇数个顶点的分量的个数. 图 $G=\left(V,E\right)$ 有完全匹配,当且仅当 $\left|V\right|$ 是偶数,并且对于顶点集的每个子集 $S$ 有 $q\left(G-S\right)\le \left|S\right|$ . 这里 $G-S$ 表示从 $G$ 中去掉 $S$ 的顶点以及与这些顶点关联的边所得到的图.

完全匹配存在于 (例如) 有偶数个顶点的完全图、完全二部图 $K_{n,m}$ 以及任意次数 $r>0$ 的正则二部图中.

3. 交错路

设 $G$ 是一个有匹配 $M$ 的图. $G$ 中的一条路 $W$ 称作交错路,当且仅当在 $W$ 中每条使得 $e\in M$ (或 $e\notin M$ ) 的边 $e$ 都有一条边 $e^{\prime }$ 跟随,并且 $e^{\prime }\notin M$ (或 $e\in M$ ). 开交错路称为递增路,当且仅当路中没有端点与 $M$ 的边关联.

4. 贝格 (Berge) 定理

图 $G$ 中匹配 $M$ 是极大的,当且仅当 $G$ 中不存在递增交错路.

如果 $W$ 是一条递增交错路,并且对应的遍历边的集合是 $E\left(W\right)$ ,那么 $M^{\prime }=$ $\left(M\setminus E\left(W\right)\right)\cup \left(E\left(W\right)\setminus M\right)$ 形成 $G$ 中一个匹配,并且 $\left|M^{\prime }\right|=\left|M_1\right|+1$ .

• 在图 5.55 中, $\left(\{1,2\},\{2,3\},\{3,4\}\right)$ 是对于匹配 $M_1$ 的递增交错路. 如上面所述得到匹配 $M_2$ ,并且 $\left|M_2\right|=\left|M_1\right|+1$ .

5. 极大匹配的确定

设 $G$ 是一个具有匹配 $M$ 的图.

a) 首先形成一个饱和匹配 $M^{\ast }$ ,并且 $M\subseteq M^{\ast }$ .

b) 选取 $G$ 的一个不与 $M^{\ast }$ 的边关联的顶点 $v$ ,并且确定 $G$ 中一条从 $v$ 开始的递增交错路.

c) 如果这样的路存在,那么上面叙述的方法产生一个匹配 $M^{\prime }$ ,并且 $\left|M^{\prime }\right|>$ $\left|M^{\ast }\right|$ . 如果这样的路不存在,那么在 $G$ 中去掉顶点 $v$ 以及所有与 $v$ 关联的边,并且重复步骤 b).

有一个埃德蒙兹 (Edmonds) 算法, 是搜索极大匹配的有效方法, 但它的叙述相当复杂 (见 [5.48]).