图论课件图的因子分解.ppt

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 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 2 把一个图按照某种方式分解成若干边不重的子图之并有把一个图按照某种方式分解成若干边不重的子图之并有重要意义。理论上，通过分解，可以深刻地揭示图的结构重要意义。理论上，通过分解，可以深刻地揭示图的结构特

2、征；在应用上，网络通信中，当有多个信息传输时，往特征；在应用上，网络通信中，当有多个信息传输时，往往限制单个信息在某一子网中传递，这就涉及网络分解问往限制单个信息在某一子网中传递，这就涉及网络分解问题。题。 一个图分解方式是多种多样的。作为图分解的典型例子，一个图分解方式是多种多样的。作为图分解的典型例子，我们介绍图的因子分解。我们介绍图的因子分解。 所谓一个图所谓一个图G的因子的因子Gi，是指至少包含，是指至少包含G的一条边的生成的一条边的生成子图。子图。 所谓一个图所谓一个图G的因子分解，是指把图的因子分解，是指把图G分解为若干个边不分解为若干个边不重的因子之并。重的因子之并。 所谓一个图

3、所谓一个图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 3 如果一个图如果一个图G能够分解为若干能够分解为若干n因子之并，称因子之并，称G是可是可n因因子分解的。子分解的。图图G1 在上图中，红色边在在上图中，红色边在G1中的导出子图，是中的导出子图，是G的一个一因的一个一因子；红色边在子；红色边在G2中的导出子图，是中的导出子图，是G的一个二因子。的一个二因子。图图G2 研究图的因子分解主要是两个方面：一是能否进行分解研究图的因子分解主要是两个方面：一是能否进行分解

4、(因子分解的存在性因子分解的存在性),二是如何分解二是如何分解(分解算法分解算法).(一一)、图的一因子分解、图的一因子分解 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。作如下排。作如下排列

5、：列：2n132:n2n-12n-2:n+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 5 图中，每行两点邻接，显然作图中，每行两点邻接，显然作成成K2n的一个一因子。的一个一因子。2n132:n2n-12n-2:n+1 然后按照图中箭头方向移动一然后按照图中箭头方向移动一个位置，又可以得到个位置，又可以得到K2n的一个一的一个一因子，不断作下去，得到因子，不断作下去，得到K2n的的2n-1个边不重的一因子，其并恰个边不重的一因子，其并恰好为好为K2n。 例例1 将将K4作一因子分解。作一因子分解。1234K441231234

6、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 61234423143121234 例例2 证明：证明：K4有唯一的一因子分解。有唯一的一因子分解。证明：由习题证明：由习题5第一题知：第一题知：K4只有只有3个不同的完美匹配。个不同的完美匹配。而而k4的每个的每个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 7 例例3 证明：证明：K2n的一因子分解数目为：的一因子分

7、解数目为：证明：由习题证明：由习题5第一题知：第一题知：K2n的不同完美匹配的个数为的不同完美匹配的个数为(2n-1)!。所以，。所以，K2n的以因子分解数目为的以因子分解数目为(2n-1)!个。即：个。即：(2 )!2!nnn(2 )!(21)!2!nnnn 例例4 证明：每个证明：每个k (k0)正则偶图正则偶图G是一可因子分解的。是一可因子分解的。 证明：因为每个证明：因为每个k (k0)正则偶图正则偶图G存在完美匹配，设存在完美匹配，设Q是它的一个一因子，则是它的一个一因子，则G-Q还是正则偶图，由归纳知，还是正则偶图，由归纳知，G可作一因子分解。可作一因子分解。 0.8 1 0.6

8、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的逆不一定成立。例如：的逆不一定成立。例如： 上图是三正则图，且可以一因子分解，但不存在圈。上图是三正则图，且可以一因子分解，但不存在圈。 0.8 1 0.6 0.4 0.2 0

9、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的割边矛盾。的割边矛盾。 注：没有割边的三正则图可能也没有一因子分解，如注：没有割边的三正则图可能也没有一因子分解，如彼得森图就是如此！尽管它存在完美匹配。彼得森图就是如此！尽管它存在完美匹配

10、。(二二)、图的二因子分解、图的二因子分解 如果一个图可以分解为若干如果一个图可以分解为若干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 10 例如，在下图中：例如，在下图中： 两个红色圈的并构成图的一个两个红色圈的并构成图的一个2因子，但不是因子，但不是H圈。圈。 一个显然结论是：一个显然结论

11、是：G能进行能进行2因子分解，其顶点度数因子分解，其顶点度数必然为偶数。必然为偶数。(注意，不一定是欧拉图注意，不一定是欧拉图) 定理定理4 K2n+1可可2因子分解。因子分解。 证明：设证明：设211221(),nnV Kv vv 作路作路11223iiiiiiiininPv vvvvvvv 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 11 其中，设其中，设Pi上的第上的第j点为点为vk，则：，则： 下标取为下标取为1, 2, 2n (mod2n)1(1)2jjki 生成圈生成圈Hi为为v2n+1与与Pi的两个端点连线。的两个端

12、点连线。 例例4 对对K7作作2因子分解。因子分解。 解：解：1162534Pv v v v v vv7v6v5v4v3v2v12213645Pv v v v v v3324156Pv v v v v vv7v6v5v4v3v2v1v7v6v5v4v3v2v1v7v6v5v4v3v2v1 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 12 定理定理5 K2n可分解为一个可分解为一个1因子和因子和n-1个个2因子之和。因子之和。 证明：设证明：设V(K2n)=v1,v2,v2n 作作n-1条路：条路：1122311iiiiiiiini

13、nPv vvvvvvv 脚标按模脚标按模2n-1计算。然后把计算。然后把v2n和和Pi的两个端点连接。的两个端点连接。 例例5 把把K6分解为一个分解为一个1因子和因子和2个个2因子分解。因子分解。v6v5v4v3v2v1 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 13 解：解：v6v5v4v3v2v1115243Pv v v v v221354Pv v v v vv6v5v4v3v2v1v6v5v4v3v2v1 定理定理6 每个没有割边的每个没有割边的3正则图是一个正则图是一个1因子和因子和1个个2因因子之和。子之和。 证明：

14、证明： 因每个没有割边的因每个没有割边的3正则图存在完美匹配正则图存在完美匹配M，显，显然，然，G-M是是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 14 定理定理7 一个连通图可一个连通图可2因子分解当且仅当它是偶数度因子分解当且仅当它是偶数度正则图。正则图。 证明：证明： 必要性显然。必要性显然。 充分性：当充分性：当G是是n阶阶2正则图时，正则图时，G本身是一个本身是一个2因子。因子。 设当设当G是是n阶阶2k正则图时，可以进行正则图时，可以进行2因子分解。当因子分解。当G是是n阶阶2k+2正则图时，由正则图

15、时，由1891年彼得森证明过的一个结论：顶年彼得森证明过的一个结论：顶点度数为偶数的任意正则图存在一个点度数为偶数的任意正则图存在一个2因子因子Q。所以，。所以，G-Q是是2k阶正则图。由归纳假设，充分性得证。阶正则图。由归纳假设，充分性得证。(三三)、图的森林因子分解、图的森林因子分解 把一个图分解为若干边不重的森林因子的和，称为图的把一个图分解为若干边不重的森林因子的和，称为图的森林因子分解。森林因子分解。 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 15 例如：例如：K5的一种森林因子分解为：的一种森林因子分解为： 主要讨论

16、：图主要讨论：图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 16 定理定理8 图图G的荫度为：的荫度为：()max1ssmGs 其中其中s是是G的子图的子图Hs的顶点数，而：的顶点数，而：max()sssmE H 例例6 求求(K(K5 5) )和和(K3,3).2111ssmsms3321ssmsms4621

17、ssmsms51031ssmsms()3G 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 172111ssmsms3211ssmsms4421ssmsms5621ssmsms3,3()3K6921ssmsms 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 18 定理定理9()2nnK,()1r srsKrs 拜内克给出了完全图和完全偶图的森林因子分解。拜内克给出了完全图和完全偶图的森林因子分解。 对于对于K2n，将其分解为，将其分解为n条路条路Pi = vivi-1vi+

18、1vi-2vi+2vi-nvi+n,脚脚标按模标按模2n计算。计算。 对于对于K2n+1，先作，先作n条路条路Pi = vivi-1vi+1vi-2vi+2vi-nvi+n,脚标按脚标按模模2n计算。在每条路外添上点计算。在每条路外添上点v2n+1的的n个森林因子；个森林因子； 然后，然后，v2n+1与与v1,v2,v2n分别相连接得一星图，这是分别相连接得一星图，这是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 19 例例7 对对K7作最小森林因子分解。作最小森林因子分解。v7v6v5v

19、4v3v2v11162534Pv v v v v v2213645Pv v v v v v3324156Pv v v v v vv3v7v6v5v4v2v1v7v6v5v4v3v2v1v7v6v5v4v3v2v1 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 20v7v6v5v4v3v2v1 例例8 证明：若证明：若n为偶数，且为偶数，且(G)n/2+1(G)n/2+1 ,则则n阶图阶图G有有3因子。因子。 证明：因证明：因(G)n/2+1(G)n/2+1 ,由狄拉克定理：由狄拉克定理：n阶图阶图G有有H圈圈C .又因又因n为偶数，

20、所以为偶数，所以C为偶圈。于是由为偶圈。于是由C可得到可得到G的的两个两个1因子。设其中一个为因子。设其中一个为F1。 考虑考虑G1=G-F1。则。则(G1)n/2。于是。于是G1中有中有H圈圈C1. 作作H=C1F1。显然。显然H是是G的一个的一个3因子。因子。 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 21 例例9 证明：一棵树证明：一棵树G有完美匹配当且仅当对所有顶点有完美匹配当且仅当对所有顶点v V(G),有：有：o(G-v)=1。 证明：证明：“必要性必要性” 一方面：若一方面：若G有完美匹配，由托特定理：有完美匹配，

21、由托特定理：O(G-v)1;1; 另一方面：若树另一方面：若树G有完美匹配，则显然有完美匹配，则显然G为偶阶树，于是为偶阶树，于是O(G-v)1;1; 所以：所以：O(G-v)=1=1。 “充分性充分性” 由于对任意点由于对任意点v V(G), 有有O(G-v)=1=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 22 设设Cv是是G-v的奇分支，又设的奇分支，又设G中由中由v连到连到G-v的奇分支的的奇分支的边为边为vu，显然，由，显然，由u连到连到G-u的奇分支的边也是的奇分支的边也是uv。 令令M=e(v):它是由它是由v

22、连到连到G-v的边，的边，v V(G) 则：则：M是是G的完美匹配。的完美匹配。vu 例例10 证明：每个证明：每个2k (k0)正则图是正则图是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 23 证明：设证明：设G是是2k连通正则图，连通正则图，V(G)=v1,v2,vn。则则G存在欧拉环游存在欧拉环游C。 由由C构造偶图构造偶图G1=(X, Y)如下：如下： X=x1,x2,xn, Y=y1,y2,yn xi与与yj在在G1=(X, Y)中连线当且仅当中连线当且仅当vi与与vj在在C中顺次相中顺次相连接。连接。 显然偶图显然偶图G1=(X, Y)是一个是一个k正则偶图。所以正则偶图。所以G1可以可以1因子分解。因子分解。 而而G1=(X, Y)的一个的一个1因子对应于因子对应于G中一个中一个2因子。所以因子。所以G可以可以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 24 作业作业 P117-118 习题习题4 ： 3, 4, 5，6，7，8，9 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 25Thank You !