《图论及其应用》课程教学课件（PPT讲稿）第五章 匹配与因子分解 5-2 图的因子分解

本次课主要内容 图的因子分解 图的一因子分解 (二) 图的二因子分解 三)、 图的森林因子分解

0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 −1 −0.5 0 0.5 1 n 1 本次课主要内容 (一)、图的一因子分解 (二)、图的二因子分解 (三)、图的森林因子分解 图的因子分解

把一个图按照某种方式分解成若干边不重的子图之并有 重要意义。理论上，通过分解，可以深刻地揭示图的结构 特征；在应用上，网络通信中，当有多个信息传输时，往 往限制单个信息在某一子网中传递，这就涉及网络分解问 题。 一个图分解方式是多种多样的。作为图分解的典型例子， 我们介绍图的因子分解。 所谓一个图G的因子G,是指至少包含G的一条边的生成 子图。 所谓一个图G的因子分解，是指把图G分解为若干个边 不重的因子之并。 所谓一个图G的n因子，是指图G的n度正则因子

0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 −1 −0.5 0 0.5 1 n 2 把一个图按照某种方式分解成若干边不重的子图之并有 重要意义。理论上，通过分解，可以深刻地揭示图的结构 特征；在应用上，网络通信中，当有多个信息传输时，往 往限制单个信息在某一子网中传递，这就涉及网络分解问 题。 一个图分解方式是多种多样的。作为图分解的典型例子， 我们介绍图的因子分解。 所谓一个图G的因子Gi，是指至少包含G的一条边的生成 子图。 所谓一个图G的因子分解，是指把图G分解为若干个边 不重的因子之并。 所谓一个图G的n因子，是指图G的n度正则因子

如果一个图G能够分解为若干n因子之并，称G是可n因 子分解的。 图G1 图G2 在上图中，红色边在G,中的导出子图，是G的一个一因 子；红色边在G,中的导出子图，是G的一个二因子。 研究图的因子分解主要是两个方面：一是能否进行分解 (因子分解的存在性)，二是如何分解（分解算法）。 (一)、图的一因子分解

0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 −1 −0.5 0 0.5 1 n 3 如果一个图G能够分解为若干n因子之并，称G是可n因 子分解的。 图G1 在上图中，红色边在G1中的导出子图，是G的一个一因 子；红色边在G2中的导出子图，是G的一个二因子。 图G2 研究图的因子分解主要是两个方面：一是能否进行分解 (因子分解的存在性),二是如何分解(分解算法). (一)、图的一因子分解

图的一个一因子实际上就是图的一个完美匹配的导出子 图。一个图能够作一因子分解，也就是它能够分解为若干 边不重的完美匹配的导出子图之并。 定理1K2n可一因子分解。 证明：把K2n的2n个顶点编号为1,2，2n。作如下排 列：

0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 −1 −0.5 0 0.5 1 n 4 图的一个一因子实际上就是图的一个完美匹配的导出子 图。一个图能够作一因子分解，也就是它能够分解为若干 边不重的完美匹配的导出子图之并。 定理1 K2n可一因子分解。 证明：把K2n的2n个顶点编号为1，2，., 2n。作如下排 列： 2n 1 3 2 : : n 2n-1 2n-2 : : n+1

图中，每行两点邻接，显然作 2n 成K2n的一个一因子。 然后按照图中箭头方向移动一 1-2 个位置，又可以得到K的一个一 因子，不断作下去，得到K的 2n-1个边不重的一因子，其并恰 n+1 好为K2n 例1将K作一因子分解

0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 −1 −0.50 0.51 n 5 图中，每行两点邻接，显然作 成 K2n的一个一因子。 2n 1 32::n 2n - 1 2n - 2 :: n+1 然后按照图中箭头方向移动一 个位置，又可以得到 K2n的一个一 因子，不断作下去，得到 K2n 的 2n - 1个边不重的一因子，其并恰 好为 K2n 。 例1 将 K 4作一因子分解。 1 2 3 4 K 4 → 4 1 2 3 1 2 3 4

例2证明：K有唯一的一因子分解。 证明：由习题5第一题知：K只有3个不同的完美匹配。 而k的每个1因子分解包含3个不同完美匹配，所以，其 1因子分解唯一

0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 −1 −0.5 0 0.5 1 n 6 1 2 3 4 4 2 3 1 4 3 1 2 1 2 3 4 例2 证明：K4有唯一的一因子分解。 证明：由习题5第一题知：K4只有3个不同的完美匹配。 而k4的每个1因子分解包含3个不同完美匹配，所以，其 1因子分解唯一

例3证明：K2的不同的一因子数目为： 2n 证明：由习题5第一题知：Kn的不同完美匹配的个数为(2n 1)。所以，K2m的一因子数目为(2n-1)!个。即： (2n-1= (2n)川 2”.nl 例4证明：每个k(k>0)正则偶图G是一可因子分解的。 证明：因为每个k(k>0)正则偶图G存在完美匹配，设 Q是它的一个一因子，则GQ还是正则偶图，由归纳知， G可作一因子分解

0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 −1 −0.5 0 0.5 1 n 7 例3 证明：K2n的不同的一因子数目为： 证明：由习题5第一题知：K2n的不同完美匹配的个数为(2n- 1)!!。所以，K2n的一因子数目为(2n-1)!!个。即： (2 )! 2 ! n n n (2 )! (2 1)!! 2 ! n n n n − = 例4 证明：每个k (k>0)正则偶图G是一可因子分解的。 证明：因为每个k (k>0)正则偶图G存在完美匹配，设 Q是它的一个一因子，则G-Q还是正则偶图，由归纳知， G可作一因子分解

定理2具有H圈的三正则图可一因子分解。 证明：先从三正则图G中抽取H圈，显然剩下边构成 G的一个一因子。而H圈显然可以分解为两个一因子。 所以G可以分解为3个一因子。 注：定理2的逆不一定成立。例如： 上图是三正则图，且可以一因子分解，但不存在H圈

0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 −1 −0.5 0 0.5 1 n 8 定理2 具有H圈的三正则图可一因子分解。 证明：先从三正则图G中抽取H圈，显然剩下边构成 G的一个一因子。而H圈显然可以分解为两个一因子。 所以G可以分解为3个一因子。 注：定理2的逆不一定成立。例如： 上图是三正则图，且可以一因子分解，但不存在H圈

定理3若三正则图有割边，则它不能一因子分解。 证明：若不然，设G的三个一因子为G1,G2,G3。不失 一般性，设割边e∈G。 显然，G-G,的每个分支必然为圈。所以在G的某个 圈中，这与e是G的割边矛盾。 注：没有割边的三正则图可能也没有一因子分解，如 彼得森图就是如此！尽管它存在完美匹配。 (二)、图的二因子分解 如果一个图可以分解为若干2度正则因子之并，称G 可以2因子分解。注意：G的一个H圈肯定是G的一个2 因子，但是G的一个2因子不一定是G的H圈。2因子可 以不连通

0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 −1 −0.5 0 0.5 1 n 9 定理3 若三正则图有割边，则它不能一因子分解。 证明：若不然，设G的三个一因子为G1 ,G2 ,G3。不失 一般性，设割边e∈G1。 显然，G-G2的每个分支必然为圈。所以e在G的某个 圈中，这与e是G的割边矛盾。 注：没有割边的三正则图可能也没有一因子分解，如 彼得森图就是如此！尽管它存在完美匹配。 (二)、图的二因子分解 如果一个图可以分解为若干2度正则因子之并，称G 可以2因子分解。注意：G的一个H圈肯定是G的一个2 因子，但是G的一个2因子不一定是G的H圈。2因子可 以不连通

例如，在下图中： 两个红色圈的并构成图的一个2因子，但不是H圈。 一个显然结论是：G能进行2因子分解，其顶点度数 必然为偶数。（注意，不一定是欧拉图） 定理4K2t1可2因子分解。 证明：设 V(K2mt1)={Y,2,.,V2n+1 作路 P=VV-IV+Vi-2Vi+2Vi-3Vi-nVitn 0

0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 −1 −0.5 0 0.5 1 n 10 例如，在下图中： 两个红色圈的并构成图的一个2因子，但不是H圈。 一个显然结论是：G能进行2因子分解，其顶点度数 必然为偶数。(注意，不一定是欧拉图) 定理4 K2n+1可2因子分解。 证明：设 V K v v v ( ) , , , 2 1 1 2 2 1 n n + + =  作路 P v v v v v v v v i i i i i i i i n i n = − + − + − − + 1 1 2 2 3