Mengzelev's Blog

图论学习笔记-图中的匹配与覆盖

Word count: 1,503 / Reading time: 6 min
2018/11/28 Share

匹配

匹配的定义

独立:若图的边集中任意两条边不邻接,则称该集合是独立的

匹配:图$G$中的边的一个独立集
$G$的匹配是一个边的集合$M={e_1,e_2,…,e_k}$,其中$e_i=u_iw_i(1\le i\le k)$,使得$u_1,u_2,…,u_k$是$U$中$k$个不同的顶点,$w_1,w_2,…,w_k$是$W$中$k$个不同的顶点。

匹配存在的条件

邻域(neighbourhood)$N(X)$:设$G$为二部图,其部集为$U$和$W$,且$|U|\le |W|$,对于$U$的非空子集$X$,$X$中所有顶点的邻域的并。

Hall’s condition/友好的(neighborly):对于$U$的任意非空子集$X$,均有$|N(X)|\ge |X|$。

定理8.3:设$G$为二部图,其部集为$U$和$W$,且$r=|U|\le |W|$。则$G$包含一个基数为$r$的匹配当且仅当$U$是友好的

定理8.4:非空有限集族${S_1,S_2,…,S_n}$有一个互异代表元系(system of distinct representative) 当且仅当 对于任一整数$k(1\le k\le n)$,集族中任意$k$个集合的并至少包含$k$个元素。

定理8.5(婚姻定理):在一个由$r$个女人和$s$个男人构成的人群中,$1\le r\le s$,在熟识的男女之间可能出现$r$对婚姻当且仅当对每个整数$k(1\le k\le r)$,任意$k$个女人共认识至少$k$个男人。

最大匹配(maximum matching):具有最大基数的匹配

完美匹配(perfect matching):阶为$2k$的图$G$存在一个基数为$k$的匹配$M$,则称该匹配$M$为完美匹配

定理8.6:任意$r$正则二部图$(r\ge 1)$均有一个完美匹配。

边的独立性参数

边独立数(edge independence number)$\alpha ‘(G)$:最大边独立集的基数

覆盖:一个顶点和与其相连的一条边

边覆盖数(edge covering number)$\beta ‘(G)$:$G$中所有边覆盖的最小基数

最小边覆盖集(minimum edge cover):具有最小基数的边覆盖集

定理8.7:对于任意不包含孤立点的$n$阶图$G$,$$\alpha’(G)+\beta’(G)=n$$

顶点的独立性参数

如果图中的一个顶点集合中任意两顶点都不邻接,则称该顶点的集合是独立

点独立数(vertex independence number)$\alpha(G)$:$G$中点独立集的最大基数,又称独立数

最大独立集(maximum independence set):图$G$中基数为$\alpha(G)$的独立集

点覆盖(vertex cover):图$G$的某个顶点子集可以覆盖$G$的所有边

点覆盖数(vertex covering number)$\beta(G)$:$G$的所有点覆盖的最小基数

最小点覆盖(minimum vertex cover):基数为$\beta(G)$的点覆盖

定理8.8:对于任意不包含孤立点的$n$阶图,$$\alpha(G)+\beta(G)=n$$

定理8.7定理8.8合称为Gallai恒等式

一般独立集比覆盖集好求

因子分解

1因子

1因子(1-factor):图$G$的1正则生成子图。
$n$阶图$G$的完美匹配$M$的诱导的子图$F[M]$是$G$的1因子。
图$G$有1因子当且仅当$G$有完美匹配。

连通分支的奇偶性就是该连通分支的阶的奇偶性
$k_O(G)$表示图$G$的奇连通分支的个数。

定理8.10:图$G$包含1因子当且仅当对于$V(G)$的任意真子集$S$,$k_O(G-S)\le |S|$。

定理8.11(Petersen定理):所有无割边的3正则图包含1因子。

定理8.12:任一至多含有两条割边的3正则图包含1因子。

分解

可因子分解的(1-factorable):若$G$有1因子$F_1,F_2,…,F_r$,使得${E(F_1),E(F_2),…,E(F_r)}$是$E(G)$的一个划分,此时我们称$G$被因子分解(factored)成1因子$F_1,F_2,…,F_r$;这些1因子构成了$G$的1因子分解(1-factorization)

任一可1因子分解的图是正则的,反之不真,反例:Peterson图

定理8.13:Petersen图是不可1因子分解的。

定理8.14:对于任意正整数$k$,完全图$K_{2k}$是可1因子分解的。

循环因子分解(cyclic factorization):如图所示,所有因子分解可以由某一个因子分解旋转一定角度得到

定理8.15:任意$r$正则的二部图$(r\ge 1)$是可1因子分解的。

2因子

2因子(2-factor):图$G$的二正则生成子图

2因子的任一连通分支是一个圈。

可2因子分解的(2-factorable):定义类似1因子

定理8.16:图$G$是可2因子分解的当且仅当存在某个正偶数$r$,是的$G$是$r$正则的。

*Hamilton因子分解(Hamilton factorization):$G$的一个2因子分解,满足该分解中所有2因子均是Hamilton圈

定理8.17:对于任一整数$k\ge 1$,完全图$K_{2k+1}$是可Hamilton分解的。
证明:构造法(如图)

因子

因子(factor):图$G$不含有孤立点的生成子图

可因子分解(factorable):因子$F_1,F_2,…,F_r$,满足${E(F_1),E(F_2),…,E(F_r)}$是$E(G)$的一个划分。

可F-因子分解的(F-factorable):若存在某个图$F$,是的每个因子$F_i\cong F$

Kirkman三元系

n阶的Kirkman三元系(Kirkman triple system):有一个基数为$n$的集合$S$,和$S$的三元子集(称为三元组(triple))族$T$,以及$T$的一个划分$\mathcal{P}$构成,且满足如下性质:

  1. $S$中任意两个不同的元素属于$T$中唯一的三元组
  2. $S$中任一元素属于划分$\mathcal{P}$的每一元素的唯一的三元组

存在一个$6k+3$阶Kirkman三元系当且仅当存在一个$K_{6k+3}$的$(2k+1)K_3$因子分解

定理8.19:$n(n\ge 3)$阶的Kirkman三元系存在当且仅当$n\equiv 3(mod 6)$,即$n=6k+3$

定理8.20:对于每个整数$k\ge 1$,完全图$K_{2k}$可因子分解为$k-1$个Hamilton圈和一个1因子。

CATALOG
  1. 1. 匹配
    1. 1.1. 匹配的定义
    2. 1.2. 匹配存在的条件
    3. 1.3. 边的独立性参数
    4. 1.4. 顶点的独立性参数
  2. 2. 因子分解
    1. 2.1. 1因子
    2. 2.2. 分解
    3. 2.3. 2因子
    4. 2.4. 因子
    5. 2.5. Kirkman三元系