图的因子分解

⚠ 转载请注明出处：作者：ZobinHuang，更新日期：May.17 2022

    本作品由 ZobinHuang 采用 知识共享署名-非商业性使用-禁止演绎 4.0 国际许可协议 进行许可，在进行使用或分享前请查看权限要求。若发现侵权行为，会采取法律手段维护作者正当合法权益，谢谢配合。

目录

有特定需要的内容直接跳转到相关章节查看即可。

正在加载目录...

引言

    把一个图按照某种方式分解成若干边不重的子图之并有重要意义。理论上, 通过分解, 可以深刻地揭示图的结构特征。应用上，网络通信中，当有多个信息传输时，往往限制单个信息在某一子网中传递，这就涉及到分解问题。

    首先我们给出定义。图 $G$ 的 因子 (Factor) 是指包含 $G$ 的至少一条边的生成子图。图 $G$ 的 $k$ 因子(k-factor)，是指图 $G$ 的 $k$ 正则生成子图。

    图 $G$ 的 因子分解 (Factorization)，是指把图 $G$ 分解为若干个边不重的因子之并。如果一个图 $G$ 能够分解为若干 $k$ 因子 之并，称 $G$ 是 $k$-因子分解 (k-Factorization)。

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

    根据上述定义，我们可以得到: 有完美匹配的图一定含有 $1$ 因子，但是不一定有 $1$ 因子分解。

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

图的 $1$ 因子分解

    根据上面的定义，图的一个 $1$ 因子就是图的一个完美匹配，也是图的一个 $1$ 正则导出子图。

    一个图能 $1$ 因子分解，就是它的边集能够分解为若干边不重的完美匹配的并，也就是它的边集能够分解为若干边不重的 $1$ 正则导出子图的并。

    下面我们给出关于 $1$ 因子分解的相关定理。

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

    证明:

    将图 $K_{2n}$ 按照上述方式进行排列。上图中, 每行两点邻接, 显然构成 $K_{2n}$ 的一个 $1$ 因子。然后按照图中箭头方向移动一个位置，又可以得到 $K_{2n}$ 的另一个 $1$ 因子。不断作下去，得到 $K_{2n}$ 的 $2n−1$ 个边不重的 $1$ 因子，其并恰好为 $K_{2n}$。

    如上图所示，是 $K_4$ 的 $1$-因子分解。由于 $K_4$ 的 $1$-因子分解包含了 $3$ 个不同的 $K_4$ 的完美匹配，而 $K_4$ 正好只有 $3$ 个完美匹配，因此 $K_4$ 的 $1$ 因子分解是唯一的。

    结合上一篇文章中对二部图的匹配的分析，可以得到如下定理：

每一个 $k$-正则二部图 $G$ 是可 $1$-因子分解的

    证明:

    由 $k$-正则二部图的性质可知，其存在完美匹配 $M$。另一方面，$G-M$ 仍然是正则二部图，因此由归纳可以知道，每一个 $k$-正则的二部图都是可以 $1$-因子分解的。

    下面给出另一个定理：

具有 $H$ 圈的 $3$ 正则图可 $1$ 因子分解

    证明:

    首先由于图是 $3$ 正则图，因此根据握手定理可知其点数一定为偶数。因此其 $H$ 圈是一个偶圈，我们可以从 $H$ 圈上导出两个不同的图的完美匹配，因此其可一因子分解。

    下面给出另一个定理:

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

    证明:

    若不然，设 $G$ 的三个 $1$ 因子为 $G_1$, $G_2$ 和 $G_3$。不失一般性，设割边 $e \in G_1$。我们从 $G$ 上删去 $G_2$，得到 $G-G_2$，此时图变为 $2$ 正则图，由于 $\delta(G) \ge 2$，则此时图中必然含有圈。因此边 $e$ 也在一个圈中，这与它是割边矛盾。

图的二因子分解

    图的 $2$ 因子指的是它的 $2$ 正则导出子图。最容易想到的一个 $2$ 因子是 $H$ 图的 $H$ 圈，但是注意如果一个图拥有 $2$ 因子，并不代表它一定有 $H$ 圈，因为 $2$ 因子有可能是不连通的。如下图所示，两个红色圈的并构成了该图的一个 $2$ 因子，但是这个 $2$ 因子并不是该图的 $H$ 圈。

    如果一个图边集可以分解为若干个 $2$ 正则导出子图的并，也即若干个 $2$ 因子的并，则称 $G$ 可以 $2$ 因子分解 (2-factorization)。

    对于 $2$ 因子分解，有一个显然的结论：

若 $G$ 能进行 $2$ 因子分解，其顶点度数必然为偶数。

    证明:

    显而易见，若一个图可 $2$ 因子分解，那么它可以导出若干个边不重的 $2$ 正则导出子图，因此每一个点的度数都必须为偶数。

$K_{2n+1}$ 可以 $2$ 因子分解。

    证明:

    设 $V(K_{2n+1}) = {v_1, v_2, ..., v_n}$，作路 $P_i=v_iv_{i-1}v_{i+1}v_{i-2}...v_{i-(n-1)}v_{i+n}$，其中路上每个点的下标取为 $1,2,...,2n \mod 2n$。基于 $P_i$ 的构造，生成圈 $H_i$ 为 $v_{2n+1}$ 与 $P_i$ 的两个端点的连线。

    不断地切换 $i$ 的值，得到若干条 $P_i$ 路，即可得到 $K_{2n+1}$ 的 $2$ 因子分解。

    举例来说，如上图所示是 $K_7$ 的 $2$ 因子分解。

    另外:

每一个 $k$ 正则图 ($k>0$) 都存在 $2$ 因子

图的森林因子分解

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

    如上图所示是 $K_5$ 的一种森林因子分解。

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

    下面有一个关于荫度的定理:

图 $G$ 的荫度为 $\sigma (G)=\max_{s} \lceil \frac{m_s}{n_s-1} \rceil$，其中 $S$ 是 $G$ 的任意子图，$n_s$ 和 $m_s$ 分别是 $S$ 的顶点数和边数。