第五章 匹配与因子分解

5.1 匹配

图的匹配相关概念

★匹配

如果 $M$ 是图 $G$ 的边子集 (不含自环), 且 $M$ 中的任意两条边没有共同顶点, 则称 $M$ 是 $G$ 的一个匹配 (matching) (或对集, 边独立集) .

$M_1=v_6{v}_7$;
$M_2=v_6{v}_7,v_1{v}_8$;
$M_3=v_6{v}_7,v_1{v}_8,v_3{v}_4$.

$M_1,M_2,M_3$ 等都是 $G$ 的匹配.

饱和点, 非饱和点

如果 $G$ 中顶点 $v$ 是 $G$ 的匹配 $M$ 中某条边的端点, 称它为 $M$ 饱和 (saturated) 点, 否则为 $M$ 非饱和 (unsaturated/exposed) 点.

★极大匹配, 最大匹配, 完美匹配

如果不能通过加边使得匹配 $M$ 增大, 称 $M$ 是图 $G$ 的极大匹配 (maximal matching);
如果 $M$ 是图 $G$ 的包含边数最多的匹配, 称 $M$ 是 $G$ 的一个最大匹配 (maximum matching);
特别地, 若最大匹配饱和了 $G$ 的所有顶点, 称它为 $G$ 的一个完美匹配 (perfect matching).

注:
(1) 极大匹配不一定是最大匹配, 最大匹配一定是极大匹配;
(2) 最大匹配不一定是完美匹配, 完美匹配一定是最大匹配.

$M$ 交错路, $M$ 增广路

如果 $M$ 是图 $G$ 的匹配, $G$ 中一条由 $M$ 中的边和非 $M$ 中的边交错形成的路, 称为 $G$ 中的一条 $M$ 交错路 ($M$ alternating path).

特别地, 若 $M$ 交错路的起点与终点是 $M$ 非饱和点, 称这种 $M$ 交错路为 $M$ 增广路 ($M$ augmenting path) 或 $M$ 可扩路.

注: 一条边不论是不是匹配边都是 $M$ 交错路.

例如在下图中:

设 $M=\{v_7{v}_8,v_3{v}_4\}$, 则: 路 $v_6{v}_7{v}_8{v}_3{v}_4$ 与 $v_1{v}_7{v}_8{v}_2$ 都是 $M$ 交错路. 其中后者是 $M$ 增广路.

注: 一条边不论是不是匹配边 (如$v_7{v}_8$) 都是 $M$ 交错路.

Berge 定理

(Berge, 1957) $G$ 的匹配 $M$ 是最大匹配, 当且仅当 $G$ 不包含 $M$ 增广路.

注: Berge 定理给我们提供了迭代扩大 $G$ 的匹配的思路(算法).

证明:

“必要性”

(反证) 若 $G$ 包含一条 $M$ 增广路 $P$, 则可令该增广路为: $P=v_0{v}_1{v}_2\cdots v_{2k}{v}_{2k+1}$.

显然, $P$ 中 $M$ 中的边比非 $M$ 中的边少一条. 于是作新的匹配 $M_1$, 它当中的边由 $P$ 中非 $M$ 中边组成. $M_1$ 中边比 $M$ 中多一条, 这与 $M$ 是 $G$ 的最大匹配矛盾.

“充分性”

(反证) 若 $M$ 不是最大匹配, 设 $M_1$ 是 $G$ 的一个最大匹配, 则 $|M_1|>|M|$.

令 $H=M_1△M$.

$H$ 中边导出图的每个分支是 (考虑由 $M_1△M$ 导出的子图):

• 由 $M_1$ 与 $M$ 中边交替组成的偶长圈 (为什么不是奇圈?); 或
• 由 $M_1$ 与 $M$ 中边交替组成的路.

在每个偶圈中, $M_1$ 与 $M$ 中边数相等; 但因 $|M_1|>|M|$, 所以, 至少有一条路 $P$, 其起点和终点都是 $M$ 非饱和点, 于是, 它是 $G$ 的一条 $M$ 可扩路. 这与条件矛盾.

5.2 二部图的匹配与覆盖

(1)在日常生活和工程技术中, 常常需求二部图的匹配.
(2)理论研究中, 二部图是一种结构相对简单的图类.

★例: 偶图匹配问题

有 7 名研究生 A, B, C, D, E, F, G 毕业寻找工作. 就业处提供的公开职位是: 会计师(a) , 咨询师(b), 编辑(c), 程序员(d), 记者(e), 秘书(f)和教师(g). 每名学生申请的职位如下:

• A: b, c;
• B: a, b, d, f, g;
• C: b, e;
• D: b, c, e;
• E: a, c, d, f;
• F: c, e;
• G: d, e, f, g

问: 学生能找到理想工作吗？

解: 如果令X={A, B, C, D, E, F, G}, Y={a, b, c, d, e, f, g}, X中顶点与Y中顶点连线当且仅当学生申请了该工作. 于是, 得到反映学生和职位之间的状态图:

问题转化为求饱和X每个顶点的一个匹配！

由后文可知:

当 $S$ 取 $X$ 中四元点集时, 若取 $S=\{A,C,D,F\}$, 则有 $3=|N(S)|<|S|=4$.

所以, 不存在饱和 $X$ 每个顶点的匹配.

需要解决的问题是: (1) 匹配是否存在? (2) 如何求出匹配?

二部图匹配存在性判定 - Hall 定理

★Hall 定理

设 $G=(X,Y)$ 是二部图, 则 $G$ 存在饱和 $X$ 每个顶点的匹配的充要条件是: 对 $\forall S\subseteq X$, 有 $|N(S)|\ge |S|$. ($N(S)$ 表示 $S$ 的邻点的集合)

注: $S$ 是 $X$ 的任意子集, 故 $S$ 可以为空集.

例

在下面二部图中, 是否存在饱和 $X=\{A,B,C,D,E,F,G\}$ 的每个顶点的匹配?

解:

(1) 当 $S$ 取 $X$ 中单点时, 容易验证: $|N(S)|>|S|$.

(2) 当 $S$ 取 $X$ 中二元点集时, 容易验证: $|N(S)|\ge |S|$.

(3) 当 $S$ 取 $X$ 中三元点集时, 容易验证: $|N(S)|\ge |S|$.

(4) 当 $S$ 取 $X$ 中四元点集时, 若取 $S=\{A,C,D,F\}$, 则有 $3=|N(S)|<|S|=4$.

所以, 不存在饱和 $X$ 每个顶点的匹配.

Hall 定理的证明

“必要性”
如果 $G$ 存在饱和 $X$ 每个顶点的匹配, 由匹配的定义, $X$ 的每个顶点在 $Y$ 中至少有一个邻点, 所以: 对 $\forall S\subseteq X$, 有 $|N(S)|\ge |S|$.

“充分性”
(反证) 若 $G$ 是满足条件的二部图, 但不存在饱和 $X$ 每个顶点的匹配.
令 $M^{\ast }$ 是 $G$ 的一个最大匹配, 但不饱和 $X$ 的顶点 $u$.

又令 $Z$ 是以 $u$ 为起点的所有 $M^{\ast }$ 交错路上点的集合.
因 $M^{\ast }$ 是最大匹配, 所以 $u$ 是所有交错路上唯一的未饱和点.
令 $S=X\cap Z$, $T=Z\cap Y$.
显然, $S-u$ 中点与 $T$ 中点在 $M^{\ast }$ 下配对, 即: $|T|=|S|-1<|S|$.
即: $|N(S)|=|T|=|S|-1<|S|$, 与条件矛盾.

注:

1. 对等部二部图来说, Hall定理也称为“婚姻定理”.
   r个女孩和r个男孩构成的人群中, 熟识的男女之间可能出现r对婚姻的充要条件是, 对每个整数k(1≤ k ≤ r), 任意k个女孩共认识至少k个男孩(Frobenius[1849-1917]于1917年首先证明, Cayley-Hamilton 定理的第一个完整证明也是由Frobenius给出).
2. Hall定理是在二部图中求最大匹配算法的理论基础, 即匈牙利算法的基础.
3. Hall (1904-1982) 英国人, 20世纪最伟大的数学家之一. 主要功绩是在代数学领域. 婚姻定理是他1935年在剑桥大学做讲师时发表的结果.

推论

若 $G$ 是 $k$ 正则二部图 ($k>0$), 则 $G$ 存在完美匹配.

证明: 一方面, 由于 $G$ 是 $k$ ($k>0$) 正则二部图, 所以 $k|X|=k|Y|$, 于是得 $|X|=|Y|$;
另一方面, 对于 $X$ 的任一非空子集 $S$, 设 $E_1$ 与 $E_2$ 分别是与 $S$ 和 $N(S)$ 关联的边集, 显然有: $E_1\subseteq E_2$,
即:$|E_1|=k|S|\le |E_2|=k|N(S)|$,
由 Hall 定理, 存在饱和 $X$ 每个点的匹配. 又 $|X|=|Y|$, 所以 $G$ 存在完美匹配.

例

证明: 每个 $k$ 方体都有完美匹配 ($k$ 大于等于 $2$).

证法一: 证明每个 $k$ 方体都是 $k$ 正则二部图.

事实上, 由 $k$ 方体的构造: $k$ 方体有 $2^k$ 个顶点, 每个顶点可以用长度为 $k$ 的二进制码来表示, 两个顶点连线当且仅当代表两个顶点的二进制码只有一位坐标不同.

如果我们划分 $k$ 方体的 $2^k$ 个顶点, 把坐标之和为偶数的顶点归入 $X$, 否则归入 $Y$. 显然, $X$ 中顶点互不邻接, $Y$ 中顶点也如此. 所以 $k$ 方体是二部图.

$k$ 方体的每个顶点度数为 $k$, 所以 $k$ 方体是 $k$ 正则二部图.

由推论: $k$ 方体存在完美匹配.

证法二: 直接在 $k$ 方体中找出完美匹配.

设 $k$ 方体顶点二进制码为 $(x_1,x_2,\dots ,x_k)$, 我们取 $(0,x_2,\dots ,x_k)$, 和 $(1,x_2,\dots ,x_k)$ 之间的全体边所成之集为 $M$.

显然, $M$ 中的边均不相邻接, 所以构成 $k$ 方体的匹配, 又容易知道: $|M|=2^{k-1}$. 所以 $M$ 是完美匹配.

思考题

(1) $3$ 方体图中不同完美匹配的个数; $9$

(2) Petersen 图中不同完美匹配的个数. $6$

例

求 $K_{2n}$ 和 $K_{n,n}$ 中不同的完美匹配的个数.

解: 我们用归纳法求 $K_{2n}$ 和 $K_{n,n}$ 中不同的完美匹配的个数.

$K_{2n}$ 的任意一个顶点有 $2n-1$ 种不同的方法被匹配. 所以 $K_{2n}$ 的不同完美匹配个数等于 $(2n-1)K_{2n-2}$, 如此推下去, 可以归纳出 $K_{2n}$ 的不同完美匹配个数为: $(2n-1)!!$.

同样的推导方法可归纳出 $K_{n,n}$ 的不同完美匹配个数为: $n!$.

例

证明树至多存在一个完美匹配.

证明: 若不然, 设 $M_1$ 与 $M_2$ 是树 $T$ 的两个不同的完美匹配, 那么 $M_1\Delta M_2\ne \Phi$, 容易知道: $T[M_1\Delta M_2]$ 每个非空部分顶点度数为 $2$, 即它存在圈, 于是推出 $T$ 中有圈, 矛盾.

图的点覆盖概念与性质

点覆盖

$G$ 的一个顶点子集 $K$ 称为 $G$ 的一个点覆盖 (vertex cover), 如果 $G$ 的每条边都至少有一个端点在 $K$ 中.

覆盖数 $\beta (G)$

$G$ 的一个包含点数最少的点覆盖称为 $G$ 的最小点覆盖, 其包含的点数称为 $G$ 的覆盖数, 记为 $\beta (G)$.

定理

设 $M$ 是 $G$ 的匹配, $K$ 是 $G$ 的点覆盖, 若 $|M|=|K|$, 则 $M$ 是最大匹配, 而 $K$ 是最小点覆盖.

证明: 设 $M^{\ast }$ 与 $K^{\ast }$ 分别是 $G$ 的最大匹配和最小点覆盖.

由匹配和点覆盖定义有: $|M^{\ast }|\le |K^{\ast }|$ (最小点覆盖至少要在每个匹配中包含一个点). 所以, 有:

$$|M|\le |M^{\ast }|\le |K^{\ast }|\le |K|$$

所以, 当 $|M|=|K|$ 时, 有 $|M|=|M^{\ast }|,|K^{\ast }|=|K|$.

即 $M$ 是最大匹配, 而 $G$ 是最小覆盖.

二部图的点覆盖与二部图匹配间的关系 - König 定理

判定一般图的点覆盖数是否不超过给定整数 $k$ 的问题是 NP-完全的(one of Karp’s 21 NP-complete problems, 1972)

★König 定理

(König,Egerváry,1931) 在二部图中, 最大匹配的边数等于最小点覆盖的顶点数.

证明: 设 $G=(X,Y)$ 是二部图, $M^{\ast }$ 和 $K^{\ast }$ 分别是 $G$ 的最大匹配和最小点覆盖. 显然有, $|M^{\ast }|\le |K^{\ast }|$.

$U$ 表示 $X$ 中 $M^{\ast }$ 非饱和点集. $Z$ 表示由 $U$ 中的顶点出发的所有 $M^{\ast }$ 交错路上的点作成的集合. 且令 $S=Z\cap X,T=Z\cap Y$.

由 $M^{\ast }$ 的最大性, $T$ 中点是 $M^{\ast }$ 饱和的, 且 $N(S)=T$.

由于 $U$ 是 $X$ 中所有未饱和的点, $X\backslash S$ 中的点都是 $M^{\ast }$ 饱和的.

现在, 令 $K^{\ast }=(X-S)\cup T$. 可以断言: $K^{\ast }=(X-S)\cup T$ 是 $G$ 的一个点覆盖.

由二部图的定义, 可能有下图中 4 种类型的边:

事实上, 若 $K^{\ast }=(X-S)\cup T$ 不是 $G$ 的一个覆盖. 则存在 $G$ 的一条边, 其一个端点在 $S$ 中, 而另一个端点在 $Y-T$ 中 (图中的蓝色虚线边, 第 4 类边), 这与 $N(S)=T$ 矛盾!

此即 $|K^{\ast }|=|M^{\ast }|$. 由定理, $K^{\ast }$ 是最小覆盖.

Rizzi在2000年给出了一个更简短的证明, 参见Romeo Rizzi, A short proof of König's matching theorem, J. Graph Theory 33 (2000) 138-139.

注: 该定理是一个极大极小定理 (Min-Max Theorem).

极大极小关系(A min-max relation): 在一个实例上关于一个极小化问题和一个极大化问题的最优解是相同的.

最大匹配 $M$ (极大化) 的边数不会超过最小点覆盖 $K$ (极小化) 的点数, 那么当 $|M|=|K|$ 时, 一定有 $M$ 是最大匹配, $K$ 是最小点覆盖 (最优解).

★例: 在布尔矩阵中的应用

矩阵的一行或一列称为矩阵的一条线.

证明: 布尔矩阵中, 包含了所有 “1” 的线的最少数目 (line rank), 等于具有性质 “任意两个 '1' 都不在同一条线上” 的 "1" 的最大数目 (term rank).

如在如下布尔矩阵中:

$$Q=\left(\begin{array}{cccc}1& 1& 1& 0\\ 0& 1& 0& 1\\ 0& 1& 0& 0\\ 0& 0& 0& 1\end{array}\right)$$

包含了所有 “1” 的线的最少数目 = 3

具有性质 “任意两个 '1' 都不在同一条线上” 的 "1" 的最大数目 = 3

证明: 设布尔阵是 $n$ 行 $m$ 列矩阵, 把它模型为一个二部图如下(二部邻接矩阵): 每行每列分别用一个点表示, $X$ 表示行点集合, $Y$ 表示列点集合, 两点连线. 当且仅当该行该列元为 $1$.

于是, 包含了所有 “1” 的线的最少数目对应二部图中的最小点覆盖数. 而具有性质 “任意两个 1 都不在同一条线上的 1 的最大数目” 对应二部图的最大匹配包含的边数.

由 König 定理, 命题得到证明.

5.3 Tutte 定理与完美匹配

Tutte 定理

(Tutte,1947) 图 $G$ 有完美匹配当且仅当对 $V(G)$ 的任意子集 $S$, 有 $o(G-S)\le |S|$.

注:

• $o(G-S)$ 表示奇分支数目 (奇分支是阶数为奇的连通分支).

• $S$ 是 $V(G)$ 的任意子集 (可以是空集).

• 若 $G$ 是偶阶图, 则 $|S|$ 与 $o(G-S)$ 有相同的奇偶性.

例

判断下图是否有完美匹配.

解: 选取 $S$ 为红色顶点, 则 $o(G-S)=6>|S|=4$. 由 Tutte 定理知该图没有完美匹配.

推论 (Petersen Theorem, 1891)

$3$ 正则无桥图存在完美匹配.

证明: 设 $S$ 是 $V$ 的任意一个非空真子集, $G_1,G_2,\dots ,G_k$ 是 $G-S$ 的所有奇分支. $m_i(1\le i\le k)$ 表示端点分属于 $S$ 和 $G_i$ 的边数.

下面分析 $m_i$.

在 $G_i$ 中, 所有顶点度和为 $2|E(G_i)|$.

在 $G_i$ 中, 每个顶点在 $G$ 中的总度数为 $3|V(G_i)|$.

所以: $m_i=3|V(G_i)|-2|E(G_i)|$.

因 $G_i$ 都是奇分支, 因此 $m_i$ 必然为奇数, 但 $G$ 无割边, 所以 $m_i\ge 3$.

$$o(G-S)=k\le \frac{1}{3}\sum _{i=1}^k{m}_i\le \frac{1}{3}\sum _{v\in S}d(v)=\frac{1}{3}\cdot 3\left|S\right|=\left|S\right|$$

由 Tutte 定理, $G$ 有完美匹配.

试证明: $k$ 正则 $k-1$ 边连通的偶阶图存在完美匹配.

注: 推论中的条件是 $G$ 存在完美匹配的充分条件而不是必要条件. 例如:

(a) 是 Sylvester graph: 无完美匹配的最小奇度正则图

那么便有下面的两方面的问题:

1. 三正则无桥图有多少个完美匹配 (结合 3 方体和 Petersen 图完美匹配个数的练习)?
2. 在什么条件下, 三正则有桥图存在完美匹配?

20 世纪 70 年代, Lovász 和 Plummer 对三正则无桥图的完美匹配个数有下面的猜想:

Lovász-Plummer conjecture. There exists a universal constant $ϵ>0$ such that for any cubic bridgeless graph $G$,

$$2^{ϵ|V(G)|}⩽|\mathcal{M}(G)|⩽2^{|V(G)|}$$

定理 (Esperet et al. 2011)

每个三正则无桥图都至少有 $2^{|V(G)|/3656}$ 个完美匹配.

(Esperet el al., Exponentially many perfect matchings in cubic graphs, Advances in Mathematics, 2011)

定理

每个至多包含 $2$ 条割边 (桥) 的三正则图都存在完美匹配.

Hint: 应用Tutte定理.

例

求证: 一棵树 $G$ 有完美匹配当且仅当对所有顶点 $v\in V(G)$, 有: $o(G-v)=1$. (V. Chungphaisan)

证明:

“必要性”

一方面: 若 $G$ 有完美匹配, 由 Tutte 定理: $o(G-v)\le 1$;

另一方面: 若树 $G$ 有完美匹配, 则显然 $G$ 为偶阶树, 于是 $o(G-v)\ge 1$;

所以: $o(G-v)=1$.

“充分性”

由于对任意点 $v\in V(G)$, 有 $o(G-v)=1$.

设 $C_v$ 是 $G-v$ 的奇分支, 又设 $G$ 中由 $v$ 连到 $G-v$ 的奇分支的边为 $vu$, 显然, 由 $u$ 连到 $G-u$ 的奇分支的边也是 $uv$.

令 $M=\{e(v)\}$, $e(v)$ 是由 $v$ 连到 $G-v$ 的奇分支的边, $v\in V(G)$.

则, $M$ 是 $G$ 的完美匹配.

5.4 因子分解

把一个图按照某种方式分解成若干边不重的子图之并有重要意义.

• (1) 理论上, 通过分解, 可以深刻地揭示图的结构特征;
• (2) 应用上, 网络通信中, 当有多个信息传输时, 往往限制单个信息在某一子网中传递, 这就涉及到分解问题.

一个图分解方式是多种多样的. 作为图分解的典型例子, 我们介绍图的因子分解.

因子和因子分解

因子

图 $G$ 的因子 (factor) 是指包含 $G$ 的至少一条边的生成子图.

图 $G$ 的 $k$ 因子 ($k$-factor), 是指图 $G$ 的 $k$ 正则生成子图.

★因子分解

图 $G$ 的因子分解 (factorization), 是指把图 $G$ 分解为若干个边不重的因子之并.

如果一个图 $G$ 能够分解为若干 $k$ 因子之并, 称 $G$ 是 $k$ 因子分解 ($k$-factorization).

注:

(1) 有完美匹配一定有 $1$ 因子, 但是不一定有 $1$ 因子分解.

(2) 完美匹配和 $1$ 因子在定义上是不同的. 事实上, 完美匹配是边集, 而 $1$ 因子是图的 $1$ 正则子图, 这两者是有区别的. 但是这两者在结构上是相同的, 所以在不致引起混淆的意义下可以认为两者相同.

在上图中, 红色边在 $G_1$ 中的导出子图, 是 $G$ 的一个一因子; 红色边在 $G_2$ 中的导出子图, 是 $G$ 的一个二因子.

研究图的因子分解主要是两个方面: 一是能否进行分解 (因子分解的存在性), 二是如何分解 (分解算法).

图的一因子分解

$1$ 因子分解

图的一个 $1$ 因子就是图的一个完美匹配. 一个图能一因子分解, 也就是它边集能够分解为若干边不重的完美匹配的并.

★定理1: $K_{2n}$ 可 $1$ 因子分解

$K_{2n}$ 可 $1$ 因子分解.

证明: 把 $K_{2n}$ 的 $2n$ 个顶点编号为 $1,2,\dots ,2n$. 作如下排列:

$2n$ 固定在左上角, 其余点逆时针方向依次递增.

上图中, 每行两点邻接, 显然构成 $K_{2n}$ 的一个 $1$ 因子.

然后按照图中箭头方向移动一个位置, 又可以得到 $K_{2n}$ 的另一个 $1$ 因子, 不断作下去, 得到 $K_{2n}$ 的 $2n-1$ 个边不重的 $1$ 因子, 其并恰好为 $K_{2n}$.

注: 若 $K_{2n}$ 是 $2n$ 个选手进行循环比赛的关系图 (竞赛图). $K_{2n}$ 的 $1$ 因子分解可以解释为一种赛程安排.

例

将 $K_4$ 作一因子分解.

例

求证: $K_4$ 有唯一的 $1$-因子分解.

证明: $K_4$ 只有 $3$ 个不同的完美匹配. 而 $K_4$ 的每个 $1$ 因子分解包含 $3$ 个不同完美匹配, 所以, 其 $1$ 因子分解唯一.

注:

(1) 事实上, $K_4$ 有唯一的 $1$-因子分解, $K_6$ 有 $6$ 个不同的 $1$-因子分解, 其它偶阶 ($>6$) 完全图的 $1$-因子分解数目随阶数增长很快, 见 https://oeis.org/A000438

(2) $1$ 因子分解的个数与完美匹配的数目是两个不同的概念. 如: $K_6$ 有 $6$ 个 $1$-因子分解 (见下图), 而 $K_6$ 有 $15$ 个不同的完美匹配.

(3) Tutte’s 8-cage or Tutte-Coxeter graph (Tutte,1947; Coxeter,1958):

$K_6$ 有 $15$ 条边和 $15$ 个不同的完美匹配. 那么 Tutte’ 8-cage 的每个顶点代表 $K_6$ 的一条边或一个完美匹配. Tutte’ 8-cage 的边连接 $K_6$ 中的完美匹配与该完美匹配中的 $3$ 条边.

• $K_6$ 的每条边都属于 $3$ 个完美匹配;
• $K_6$ 的每个完美匹配都包含 $3$ 条边.

由上知, Tutte’s 8-cage 是二部图 ($3$ 正则距离传递图, 共 $13$ 个).

Tutte’s 8-cage 是 $3$ 正则围长为 $8$ (Hint: 排除 $4$ 长圈和 $6$ 长圈), 顶点数最少唯一的图, 亦即 $(3,8)$-cage.

例

证明: 每个 $k(k>0)$ 正则二部图 $G$ 是可 $1$ 因子分解的.

证明: 因 $k(k>0)$ 正则二部图 $G$ 存在完美匹配 $M$, 则 $G-M$ 仍然是正则二部图. 由归纳知, $G$ 可一因子分解.

★定理2

具有 H 圈的三正则图可一因子分解.

证明: 先从 $G$ 中找出 H 圈, 显然 $G-E(H)$ 是 $1$ 因子. 而 H 圈是偶圈, 它显然可以分解为两个 $1$ 因子. 所以 $G$ 可以分解为 $3$ 个 $1$ 因子.

注: 定理 2 的逆不一定成立. 例如:

上图是 $3$ 正则图, 且可以 $1$ 因子分解, 但不存在 H 圈.

定理3

若三正则图有割边, 则它不能 $1$ 因子分解.

证明: 若不然, 设 $G$ 的三个一因子为 $G_1,G_2,G_3$. 不失一般性, 设割边 $e\in G_1$.

显然, $G-G_2$ 的每个分支必然为圈. 所以 $e$ 在 $G$ 的某个圈中, 这与 $e$ 是 $G$ 的割边矛盾.

注: 没有割边的 $3$ 正则图可能也没有一因子分解, Petersen 图就是如此 (Petersen, 1898)! 尽管它存在完美匹配.

图的二因子分解

$2$ 因子分解

如果一个图边集可以分解为若干个 $2$ 因子的并, 称 $G$ 可以 $2$ 因子分解 ($2$-factorization).

注: $G$ 的一个 H 圈肯定是 $G$ 的一个 $2$ 因子, 但是 $G$ 的一个 $2$ 因子不一定是 $G$ 的 H 圈 ($2$ 因子可以不连通).

在下图中:

两个红色圈的并构成图的一个 $2$ 因子, 但不是 H 圈.

注: 一个显然结论是: $G$ 能进行 $2$ 因子分解, 其顶点度数必然为偶数. (注意, 不一定连通, 可能不是欧拉图)

★定理: $K_{2n+1}$ 可 $2$ 因子分解

(Walecki, 1890) $K_{2n+1}$ 可 $2$ 因子分解.

证明: 设 $V(K_{2n+1})=\{v_1,v_2,\cdots ,v_{2n+1}\}$.

作路

$$P_i=v_i{v}_{i-1}{v}_{i+1}{v}_{i-2}{v}_{i+2}{v}_{i-3}\cdots v_{i-(n-1)}{v}_{i+(n-1)}{v}_{i-n},1\le i\le n$$

下标取为 $1,2,\dots ,2n(\mathrm{m}\mathrm{o}\mathrm{d}2n)$.

生成圈 $H_i$ 为 $v_{2n+1}$ 与 $P_i$ 的两个端点连线.

例: $K_7$ 分解

对 $K_7$ 进行 $2$ 因子分解.

解:

$$\begin{gathered} P_1=v_1{v}_6{v}_2{v}_5{v}_3{v}_4 \\ {P}_2=v_2{v}_1{v}_3{v}_6{v}_4{v}_5 \\ {P}_3=v_3{v}_2{v}_4{v}_1{v}_5{v}_6 \end{gathered}$$

则 $K_7$ 的三个 $2$ 因子 ($2$ 因子分解) 为:

★定理: $K_{2n}$ 分解

$K_{2n}$ 可分解为一个 $1$ 因子和 $n-1$ 个 $2$ 因子之和.

证明: 设 $V(K_{2n})=\{v_1,v_2,\dots ,v_{2n}\}$.

作 $n-1$ 条路:

$$P_i=v_i{v}_{i-1}{v}_{i+1}{v}_{i-2}{v}_{i+2}{v}_{i-3}{v}_{i-3}...v_{i-n-1}{v}_{i+n-1}$$

下标按模 $2n-1$ 计算. 然后把 $v_{2n}$ 和 $P_i$ 的两个端点连接.

例: $K_6$ 分解

把 $K_6$ 分解为一个 $1$ 因子和 $2$ 个 $2$ 因子分解.

解: $P_1=v_1{v}_5{v}_2{v}_4{v}_3,P_2=v_2{v}_1{v}_3{v}_5{v}_4$.

★定理

每个没有割边的 $3$ 正则图是一个 $1$ 因子和 $1$ 个 $2$ 因子之和.

证明: 因每个没有割边的 $3$ 正则图存在完美匹配 $M$, 显然, $G-M$ 是 $2$ 因子.

定理 (Petersen, 1891)

每个 $k$ 正则图 ($k>0$ 是偶数) 都存在 $2$ 因子.

定理

一个连通图可 $2$ 因子分解当且仅当它是偶数度正则图.

证明: 必要性显然.

充分性: 当 $G$ 是 $n$ 阶 $2$ 正则图时, $G$ 本身是一个 $2$ 因子.

设当 $G$ 是 $n$ 阶 $2k$ 正则图时, 可以进行 $2$ 因子分解. 当 $G$ 是 $n$ 阶 $2k+2$ 正则图时, 由 1891 年彼得森证明过的一个结论: 顶点度数为偶数的任意正则图存在一个 $2$ 因子 $Q$. 所以, $G-Q$ 是 $2k$ 阶正则图. 由归纳假设, 充分性得证.

图的森林因子分解

森林因子分解

把一个图分解为若干边不重的生成森林 (因子) 的并, 称为图的森林因子分解. (用来衡量边的稠密程度)

$K_5$ 的一种森林因子分解为:

荫度 $\sigma (G)$

森林因子分解的主要问题: 图 $G$ 分解为边不重的森林因子的最少数目问题, 称这个最小数目为 $G$ 的荫度 (arboricity), 记为 $\sigma (G)$.

定理 (Nash-Williams, 1961)

Nash-Williams 得到了图的荫度计算公式.

图 $G$ 的荫度为:

$$\sigma (G)=\underset{s}{\max }\lceil \frac{m_s}{n_s-1}\rceil$$

其中 $S$ 是 $G$ 的任意子图, $n_s$ 和 $m_s$ 分别是 $S$ 的顶点数和边数.

5.5 最优匹配与匈牙利算法

二部图中寻找完美匹配

问题: 设 $G=(X,Y),|X|=|Y|$, 在 $G$ 中求一完美匹配 $M$.

基本思想: 从任一初始匹配 $M_0$ 出发, 通过寻求一条 $M_0$ 增广路 $P$, 令 $M_1=M_0\Delta E(P)$, 得到比 $M_0$ 更大的匹配 $M_1$ (迭代思想).

$M$ 可扩路的寻找方法: 1965 年, Edmonds 首先提出用扎根于 $M$ 非饱和点 $u$ 的 $M$ 交错树的生长来求 $M$ 可扩路.

$M$ 交错树

设 $G=(X,Y)$, $M$ 是 $G$ 的匹配, $u$ 是 $M$ 的非饱和点. 称树 $H$ 是 $G$ 的扎根于点 $u$ 的 $M$ 交错树 ($M$-augmenting tree), 如果:

1. $u\in V(H)$;
2. 对任意 $v\in V(H),(u,v)$ 路是 $M$ 交错路.

$M$ 交错树的生长

扎根于 $M$ 非饱和点 $u$ 的 $M$ 交错树的生长:

假如 $H$ 是扎根于 $M$ 非饱和点 $u$ 的 $M$ 交错树. 它有两种情形:

情形1: $H$ 包含除 $u$ 外的 $M$ 非饱和点 (存在增广路). 那么可以修改匹配 $M$, 得到新的 $M$ 交错树.

情形2: 除点 $u$ 外, $H$ 中所有点为 $M$ 饱和点, 且在 $M$ 上配对. 那么继续进行如下判断:

令 $S=V(H)\cap X,T=V(H)\cap Y$, 显然: $T\subseteq N(S)$.

(1) 若 $N(S)=T$:

由于 $S-\{u\}$ 中点与 $T$ 中点配对, 所以有: $|T|=|S|-1$, 于是有: $|N(S)|=|S|-1<|S|$. 由 Hall 定理, $G$ 中不存在完美匹配;

(2) 若 $T\subset N(S)$:

令 $y\in N(S)-T$, 则在树 $H$ 中存在点 $x$ 与 $y$ 邻接. 因为 $H$ 的所有点, 除 $u$ 外, 均在 $M$ 下配对. 所以, 都有 $xy\notin M$.

当然, $y$ 可能为 $M$ 非饱和点, 也可能为 $M$ 饱和点.

• $y$ 是 $M$ 非饱和点 (同情形1, 扩张 $M$ 后, 在新匹配下生成交错树).

• $y$ 是 $M$ 饱和点 ($S$ 与 $T$ 均已迭代变化, 继续判断 $N(S)=T?$).

反复进行上述过程, 最终判定 $G$ 是否有完美匹配或者求出完美匹配.

根据上面讨论, 可设计求二部图的完美匹配算法.

二部图完美匹配算法 - 匈牙利算法

设 $M$ 是初始匹配. $H$ 是扎根于 $M$ 非饱和点 $u$ 的交错树. 令: $S=V(H)\cap X,T=V(H)\cap Y$.

(a) 若 $M$ 饱和 $X$ 所有顶点, 停止. 否则, 设 $u$ 为 $X$ 中 $M$ 非饱和顶点, 置 $S=\{u\},T=\Phi$;

(b) 若 $N(S)=T$, 则 $G$ 中不存在完美匹配. 否则设 $y\in N(S)-T$.

(c) 若 $y$ 为 $M$ 饱和点, 且 $yz\in M$, 置 $S=S\cup \{z\},T=T\cup \{y\}$, 转 (b). 否则, 设 $P$ 为 $M$ 可扩路, 置 $M_1=M\Delta E(P)$, 转 (a).

例

讨论下图 $G=(X,Y)$ 是否有完美匹配.

解: 取初始匹配 $M=\{x_1{y}_1,x_2{y}_3\}$.

(a) $S=\{x_3\},T=\Phi$;

(b) $N(S)=\{y_2,y_3\},N(S)\ne T$, 取 $y_2\in N(S)-T$.

(c) $y_2$ 为 $M$ 非饱和点, 加上 $y_2$ 和边 $x_3{y}_2$ 生长树 $H$. 此时, 置 $M=M\Delta E(P)=\{x_1{y}_1,x_2{y}_3,x_3{y}_2\}$.

(a) $S=\{x_4\},T=\Phi$;

(b) $N(S)=\{y_2,y_3\}$, $N(S)\ne T$, 取 $y_2\in N(S)-T$.

(c) $y_2$ 为 $M$ 饱和点, $y_2{x}_3\in M$. 此时, 置 $S=S\cup \{x_3\}=\{x_3,x_4\}$.

(b) $N(S)=\{y_2,y_3\}\ne T$, 取 $y_3\in N(S)-T$.

(c) $y_3$ 为 $M$ 饱和点, $x_2{y}_3\in M$. 此时, 置 $S=S\cup \{x_2\}=\{x_2,x_3,x_4\}$, $T=T\cup y_3=\{y_2,y_3\}$.

(b) $N(S)=\{y_2,y_3\}=T$, 所以, $G$ 无完美匹配.

匈牙利算法复杂性分析

1. 最多循环 $|X|$ 次可以找到完美匹配;
2. 初始匹配最多扩张 $|X|$ 次可以找到完美匹配;
3. 每次生长树的生长至多 $2|X|-1$ 次.

所以, 算法复杂性为 $O(|X{|}^3)$, 是好算法.

二部图中寻找最大匹配

问题: 在一般二部图上求最大匹配 $M$.

分析: 使用匈牙利算法求完美匹配时, 当在扎根于 $M$非饱和点 $u$ 的交错树上有 $|N(S)|<|S|$ 时, 由 Hall 定理, 算法停止. 要求出最大匹配, 应该继续检查 $X-S$ 是否为空, 如果不为空, 则检查是否在其上有 $M$ 非饱和点.一直到所有 $M$ 非饱和点均没有 $M$ 可扩路才停止.

二部图中寻找最大匹配算法

设 $M$ 是 $G=(X,Y)$ 的初始匹配.

(1) 置 $S=\Phi ,T=\Phi$;

(2) 若 $X-S$ 已经 $M$ 饱和, 停止; 否则, 设 $u$ 是 $X-S$ 中的一非饱和顶点, 置 $S=S\cup \{u\}$.

(3) 若 $N(S)=T$, 转 (5); 否则, 设 $y\in N(S)-T$.

(4) 若 $y$ 是 $M$ 饱和的, 设 $yz\in M$, 置 $S=S\cup z$, $T=T\cup \{y\}$, 转 (3); 否则, 存在 $(u,y)$交错路是 $M$ 可扩路 $P$, 置 $M=M\Delta E(P)$, 转 (1).

(5) 若 $X-S=\Phi$, 停止; 否则转 (2).

注: 事实上, 1973 年 John Hopcroft 和 Richard Karp 给出了时间复杂度为 $O(m\sqrt{n})$ 的最大匹配算法 (在一次迭代中找出尽可能多的增广路, 而不像匈牙利算法不是一次只给出一条).

★完全二部图的最优匹配

最优匹配问题

设 $G=(X,Y)$ 是边赋权完全二部图, 且 $X=\{x_1,x_2,\dots ,x_n\},Y=\{y_1,y_2,\dots ,y_n\},w_{ij}=w(x_i{y}_j)$. 在 $G$ 中求出一个具有最大权值的完美匹配.

由于 $K_{n,n}$ 有 $n!$ 个不同完美匹配, 所以枚举计算量是 $n!$.

在匈牙利算法的基础上, Kuhn (1955) 与 Munkres (1957) 提出了上面问题的好算法.

可行顶点标号

设 $G=(X,Y)$ 是边赋权完全二部图. 若在顶点集 $X\cup Y$ 上的实值函数 $l$ 适合下述条件: 对任意的 $x\in X,y\in Y$, 有

$$l(x)+l(y)\ge w(xy)$$

称 $l$ 是 $G$ 的可行顶点标号 (feasible vertex labelling).

• 可行顶点标号是这样的顶点标号, 它使每条边的两端点的标号之和至少与这条边的权一样大.
• 可行顶点标号形式上类似于三角不等式 (triangle inequality).

对于任意的赋权完全二部图 $G$, 均存在 $G$ 的可行顶点标号. 事实上, 设:

$$\{\begin{array}{l}l(x)={\max }_{y\in Y}w(xy),\text{ 若 }x\in X,\\ l(y)=0,\text{ 若 }y\in Y.\end{array}$$

则 $l$ 是 $G$ 的一个可行顶点标号.

相等子图

设 $l$ 是赋权完全二部图 $G=(X,Y)$ 的可行顶点标号, 令:

$$E_l=\{xy\in E(G)|l(x)+l(y)=w(xy)\}$$

称 $G_l=G[E_l]$ 为 $G$ 的对应于 $l$ 的相等子图 (equality subgraph).

定理

设 $l$ 是赋权完全二部图 $G=(X,Y)$ 的可行顶点标号, 若相等子图 $G_l$ 有完美匹配 $M^{\ast }$, 则 $M^{\ast }$ 是 $G$ 的最优匹配.

证明: 设 $M^{\ast }$ 是 $G_l$ 的完美匹配, 则:

$$w(M^{\ast })=\sum _{e\in M^{\ast }}w(e)=\sum _{v\in V(G)}l(v)$$

又设 $M$ 是 $G$ 的任一完美匹配, 则:

$$w(M)=\sum _{e\in M}w(e)\le \sum _{v\in V(G)}l(v)$$

所以, $w(M^{\ast })\ge w(M)$. 即 $M^{\ast }$ 是 $G$ 的最优匹配.

根据上面定理, 若找到一种恰当的可行顶点标号, 使得对应的相等子图有完美匹配 $M^{\ast }$, 则求出了 $G$ 的最优匹配.

最优匹配算法

Kuhn 采用顶点标号修改策略, 找到了求最优匹配好算法, 具体如下:

给一初始顶点标号 $l$, 在 $G_l$ 中任选一个匹配 $M$.

(1) 若 $X$ 是 $M$ 饱和的, 则 $M$ 是最优匹配. 否则, 令 $u$ 是一个 $M$ 非饱和点, 置: $S=u,T=\varphi$.

(2) 若 $N_{G_l}(S)\supset T$, 转 (3). 否则 (即 $N(S)=T$ ), 计算:

$${\alpha }_l=\underset{\begin{array}{c}x\in S\\ y\notin T\end{array}}{\min }\{l(x)+l(y)-w(xy)\}$$

$$\hat{l}=\{\begin{array}{l}l(v)-{\alpha }_l,v\in S\\ l(v)+{\alpha }_l,v\in T\\ l(v),\text{ 其它 }\end{array}$$

给出新的可行顶点标号, 在新标号下重新开始.

(3) 对 $G_l$ , 在 $N(S)-T$ 中选择点 $y$.
若 $y$ 是 $M$ 饱和的, $yz\in M$, 则置 $S=S\cup z,T=T\cup y$ 转 (2).
否则, 设 $P$ 是 $G_l$ 中 $M$ 可扩路, 置 $M=M\Delta E(P)$, 转 (1).

注:
(1) 该算法把匈牙利算法用于其中, 主要是用来判定和求完美匹配.
(2) 求一般的赋权二部图 (非完全) 的最大匹配, 将不存在的边用权值为 $0$ 的边代替后得到完全二部图后即可用该算法.

例

设如下矩阵是赋权完全二部图 $G$ 的权值矩阵, 求出其最优匹配.

$$W=\left(\begin{array}{ccccc}3& 5& 5& 4& 1\\ 2& 2& 0& 2& 2\\ 2& 4& 4& 1& 0\\ 0& 1& 1& 0& 0\\ 1& 2& 1& 3& 3\end{array}\right)$$

解: 给出初始可行顶点标号 $l$ 为:

$$W=\begin{array}{cc}\left(\begin{array}{ccccc}3& 5& 5& 4& 1\\ 2& 2& 0& 2& 2\\ 2& 4& 4& 1& 0\\ 0& 1& 1& 0& 0\\ 1& 2& 1& 3& 3\end{array}\right)& \begin{array}{c}5\\ 2\\ 4\\ 1\\ 3\end{array}\\ \begin{array}{ccccc}0& 0& 0& 0& 0\end{array}& \end{array}$$

对应的相等子图 $G_l$ 为:

给出初始匹配 $M$ 为:

(1) $u=x_4$ 为 $M$ 非饱和顶点.置: $S=\{x_4\},T=\varphi$

(2) $N_{G_l}(S)=\{y_2,y_3\}\supset T$

(3) 取: $y_2\in N_{G_l}(S)-T$, $y_2$ 为饱和顶点, $y_2{x}_1\in M$, 于是: $S=\{x_1,x_4\},T=\{y_2\}$

(2) $N_{G_l}(S)=\{y_2,y_3\}\supset T$

(3) 取: $y_3\in N_{G_l}(S)-T$, $y_3$为饱和顶点, $y_3{x}_3\in M$, 于是: $S=\{x_1,x_3,x_4\},T=\{y_2,y_3\}$

(2) $N_{G_l}(S)=\{y_2,y_3\}=T$, 于是修改标号: ${\alpha }_l={\min }_{\begin{array}{c}x\in S\\ y\notin T\end{array}}\{l(x)+l(y)-w(xy)\}=1({\alpha }_l>0)(x\in x_1,x_3,x_4,y\in y_1,y_4,y_5)$

由 $\hat{l}=\{\begin{array}{l}l(v)-{\alpha }_l,v\in S\\ l(v)+{\alpha }_l,v\in T\\ l(v),\text{ 其它 }\end{array}$ 得新标号为

$$W=\begin{array}{cc}\left(\begin{array}{ccccc}3& 5& 5& 4& 1\\ 2& 2& 0& 2& 2\\ 2& 4& 4& 1& 0\\ 0& 1& 1& 0& 0\\ 1& 2& 1& 3& 3\end{array}\right)& \begin{array}{c}5\to 4\\ 2\\ 4\to 3\\ 1\to 0\\ 3\end{array}\\ \begin{array}{ccccc}0& 0& 0& 0& 0\end{array}& \\ \begin{array}{ccccc}& \downarrow & \downarrow & & \end{array}& \\ \begin{array}{ccccc}& 1& 1& & \end{array}& \end{array}$$

在新标号下 (重新找相等子图): 红色边为新加入的边; $x_2{y}_2$ 不再出现.

继续使用算法后得:

最优匹配权值为 $14$.

一般图的完美匹配算法

Unfortunately, 用匈牙利算法求解一般图的完美匹配时, 由于奇圈的存在, 可能导致出现无穷多个交错路. Edmonds提出了开花算法 (Blossom algorithm) 克服这个缺点.

Overview: 开花算法在匈牙利算法的基础上, 将奇圈收缩为一个点然后再使用匈牙利算法找增广路.