MatchingsIn

定义

因子 (factor): 一个图的导出子图.

k-因子 (k-factor): k-正则的导出子图.

注

1-factor 基本等价于完美匹配. 只是因子更偏向于子图, 完美匹配偏向于边.

3-正则图含有完美匹配, 那么能分解为 1-factor 和 2-factor.

定义

奇分支 (Odd component): 奇数个点的连通分支, 记其个数为 o(H).

Tutte’s Condition: 对于任意 $S\subset V(G)$ , $o(G-S)\leqslant |S|$ .

引理

设 $G$ 满足 Tutte 条件, 设 $G'=G+e$ , 那么 $G'$ 仍满足条件.

证明

因为加边不会让奇分支数量增加.

定理 Tutte

一个图含有 1-因子当且仅当对任意 $S\subset V(G)$ , 有 $o(G-S)\leqslant |S|$ .

证明

" $\Rightarrow$ ": 每个奇分支都至少有一条完美匹配的边与 S 相连, 且不同奇分支对应的点不同.

" $\Leftarrow$ ": 反证法, 假设存在 $G$ 满足条件但不含有 1-因子, 且再增加任意边都会包含一个 1-因子 (这样假设是合理的, 因为你可以不断加边直到满足, 由引理可知加边不影响 Tutte 条件, 然后可以再反推回去每个图都含有 1-因子).

设 $U=\{v\in V(G): d(v)=n(G)-1\}$

(1) G-U 是若干团的并. $o(G-U)$ 为奇团个数, 又满足 $o(G-U)\leqslant |U|$ , 再结合 $U$ 的定义可知存在 1-因子.

(2) 若存在非完全的分支 $H$ , 那么存在 $x,y,z\in H$ , $xy,yz\in E(H),xz\notin E(H)$ 且 $y\notin U$ .

因此存在 $w\notin G$ , $yw\notin E(G)$ .

根据假设 $G+xz$ , $G+yw$ 均有完美匹配, 记作 $M_1$ , $M_2$ . 考虑 $M_1\Delta M_2$ , 有引理 \ref{lemma::对称差} 及完美匹配性质可知对称差只包含偶环.

如果 $yw,xz$ 不在同一个偶环中, 那只要这两个偶环都取另一个匹配即可得到一个原图中的完美匹配.

如果 $yw,xz$ 在同一个偶环中, 那么 $xz, yw$ 一定存在在该偶环的两个不同的完美匹配中.

考虑加入 $yz$ 那么可以拆成一个路和一个偶环, 且最大匹配也是完美匹配.

推论 Petersen

任意 3-regular 图如果没有割边那么就有 1-因子.

证明

考虑任意点集 $S$ , $G-S$ 的奇分支记作 $H_1,H_2,\ldots$ , 则有 $H_1,H_2,\ldots$ 在 $G$ 中互不直接相连.

考虑 $H_i$ 与 $S$ 的边数记作 $m_i$ , 那么 $m_i=3n(H_i)-2e(H_i)\geqslant 1$ 且是奇数, 又整个图无割边所以 $m_i\geqslant 3$ , 所以

3o(G-S)\leqslant\sum m_i\leqslant\sum\limits_{v\in S} d(v)\leqslant3 |S|

于是 $o(G-S)\leqslant |S|$ . 满足 tutte 条件.

定理 Petersen

任意 2k-regular 图有 2-因子.

证明

考虑一个 2k-regular 连通图, 记作 K, 设有 n 个点. 由于是 2k 正则的, 所以存在欧拉回路记作 C.

Matchings in general graphs #