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

,单击此处编辑母版标题样式,*,*,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,1,图论及其应用,应用数学学院,2,本次课主要内容,(,一,),、图的一因子分解,(,二,),、图的二因子分解,(,三,),、图的森林因子分解,图的因子分解,3,把一个图按照某种方式分解成若干边不重的子图之并有重要意义。理论上，通过分解，可以深刻地揭示图的结构特征；在应用上，网络通信中，当有多个信息传输时，往往限制单个信息在某一子网中传递，这就涉及网络分解问题。,一个图分解方式是多种多样的。作为图分解的典型例子，我们介绍图的因子分解。,所谓一个图,G,的因子,G,i,，是指至少包含,G,的一条边的生成子图。,所谓一个图,G,的因子分解，是指把图,G,分解为若干个边不重的因子之并。,所谓一个图,G,的,n,因子，是指图,G,的,n,度正则因子。,4,如果一个图,G,能够分解为若干,n,因子之并，称,G,是可,n,因子分解的。,图,G,1,在上图中，红色边在,G,1,中的导出子图，是,G,的一个一因子；红色边在,G,2,中的导出子图，是,G,的一个二因子。,图,G,2,研究图的因子分解主要是两个方面：一是能否进行分解,(,因子分解的存在性,),二是如何分解,(,分解算法,).,(,一,),、图的一因子分解,5,图的一个一因子实际上就是图的一个完美匹配。一个图能够作一因子分解，也就是它能够分解为若干边不重的完美匹配之并。,定理,1 K,2n,可一因子分解。,证明：把,K,2n,的,2n,个顶点编号为,1,，,2,，,2n,。作如下排列：,2n,1,3,2,:,:,n,2n-1,2n-2,:,:,n+1,6,图中，每行两点邻接，显然作成,K,2n,的一个一因子。,2n,1,3,2,:,:,n,2n-1,2n-2,:,:,n+1,然后按照图中箭头方向移动一个位置，又可以得到,K,2n,的一个一因子，不断作下去，得到,K,2n,的,2n-1,个边不重的一因子，其并恰好为,K,2n,。,例,1,将,K,4,作一因子分解。,1,2,3,4,K,4,4,1,2,3,1,2,3,4,7,1,2,3,4,4,2,3,1,4,3,1,2,1,2,3,4,例,2,证明：,K,4,有唯一的一因子分解。,证明：由习题,5,第一题知：,K,4,只有,3,个不同的完美匹配。而,k,4,的每个,1,因子分解包含,3,个不同完美匹配，所以，其,1,因子分解唯一。,8,例,3,证明：,K,2n,的一因子分解数目为：,证明：由习题,5,第一题知：,K,2n,的不同完美匹配的个数为,(2n-1)!,。所以，,K,2n,的以因子分解数目为,(2n-1)!,个。即：,例,4,证明：每个,k(k0),正则偶图,G,是一可因子分解的。,证明：因为每个,k(k0),正则偶图,G,存在完美匹配，设,Q,是它的一个一因子，则,G-Q,还是正则偶图，由归纳知，,G,可作一因子分解。,9,定理,2,具有,H,圈的三正则图可一因子分解。,证明：先从三正则图,G,中抽取,H,圈，显然剩下边构成,G,的一个一因子。而,H,圈显然可以分解为两个一因子。所以,G,可以分解为,3,个一因子。,注：定理,2,的逆不一定成立。例如：,上图是三正则图，且可以一因子分解，但不存在圈。,10,定理,3,若三正则图有割边，则它不能一因子分解。,证明：若不然，设,G,的三个一因子为,G,1,G,2,G,3,。不失一般性，设割边,e G,1,。,显然，,G-G,2,的每个分支必然为圈。所以,e,在,G,的某个圈中，这与,e,是,G,的割边矛盾。,注：没有割边的三正则图可能也没有一因子分解，如彼得森图就是如此！尽管它存在完美匹配。,(,二,),、图的二因子分解,如果一个图可以分解为若干,2,度正则因子之并，称,G,可以,2,因子分解。注意：,G,的一个,H,圈肯定是,G,的一个,2,因子，但是,G,的一个,2,因子不一定是,G,的,H,圈。,2,因子可以不连通。,11,例如，在下图中：,两个红色圈的并构成图的一个,2,因子，但不是,H,圈。,一个显然结论是：,G,能进行,2,因子分解，其顶点度数必然为偶数。,(,注意，不一定是欧拉图,),定理,4 K,2n+1,可,2,因子分解。,证明：设,作路,12,其中，设,P,i,上的第,j,点为,v,k,，则：,下标取为,1,2,2n(mod2n),生成圈,H,i,为,v,2n+1,与,P,i,的两个端点连线。,例,4,对,K,7,作,2,因子分解。,解：,v,7,v,6,v,5,v,4,v,3,v,2,v,1,v,7,v,6,v,5,v,4,v,3,v,2,v,1,v,7,v,6,v,5,v,4,v,3,v,2,v,1,v,7,v,6,v,5,v,4,v,3,v,2,v,1,13,定理,5 K,2n,可分解为一个,1,因子和,n-1,个,2,因子之和。,证明：设,V(K,2n,)=,v,1,v,2,v,2n,作,n-1,条路：,脚标按模,2n-1,计算。然后把,v,2n,和,P,i,的两个端点连接。,例,5,把,K,6,分解为一个,1,因子和,2,个,2,因子分解。,v,6,v,5,v,4,v,3,v,2,v,1,14,解：,v,6,v,5,v,4,v,3,v,2,v,1,v,6,v,5,v,4,v,3,v,2,v,1,v,6,v,5,v,4,v,3,v,2,v,1,定理,6,每个没有割边的,3,正则图是一个,1,因子和,1,个,2,因子之和。,证明：,因每个没有割边的,3,正则图存在完美匹配,M,，显然，,G-M,是,2,因子。,15,定理,7,一个连通图可,2,因子分解当且仅当它是偶数度正则图。,证明：,必要性显然。,充分性：当,G,是,n,阶,2,正则图时，,G,本身是一个,2,因子。,设当,G,是,n,阶,2k,正则图时，可以进行,2,因子分解。当,G,是,n,阶,2k+2,正则图时，由,1891,年彼得森证明过的一个结论：顶点度数为偶数的任意正则图存在一个,2,因子,Q,。所以，,G-Q,是,2k,阶正则图。由归纳假设，充分性得证。,(,三,),、图的森林因子分解,把一个图分解为若干边不重的森林因子的和，称为图的森林因子分解。,16,例如：,K,5,的一种森林因子分解为：,主要讨论：图,G,分解为边不重的森林因子的最少数目问题，称这个最少数目为,G,的荫度，记为,(G),。,纳什,-,威廉斯得到了图的荫度计算公式。,17,定理,8,图,G,的荫度为：,其中,s,是,G,的子图,H,s,的顶点数，而：,例,6,求,(K,5,),和,(K,3,3,).,18,19,定理,9,拜内克给出了完全图和完全偶图的森林因子分解。,对于,K,2n,，将其分解为,n,条路,P,i,=v,i,v,i-1,v,i+1,v,i-2,v,i+2,v,i-n,v,i+n,脚标按模,2n,计算。,对于,K,2n+1,，先作,n,条路,P,i,=v,i,v,i-1,v,i+1,v,i-2,v,i+2,v,i-n,v,i+n,脚标按模,2n,计算。在每条路外添上点,v,2n+1,的,n,个森林因子；,然后，,v,2n+1,与,v,1,v,2,v,2n,分别相连接得一星图，这是,G,的最后一个森林因子。,20,例,7,对,K,7,作最小森林因子分解。,v,7,v,6,v,5,v,4,v,3,v,2,v,1,v,3,v,7,v,6,v,5,v,4,v,2,v,1,v,7,v,6,v,5,v,4,v,3,v,2,v,1,v,7,v,6,v,5,v,4,v,3,v,2,v,1,21,v,7,v,6,v,5,v,4,v,3,v,2,v,1,例,8,证明：若,n,为偶数，且,(G)n/2+1,则,n,阶图,G,有,3,因子。,证明：因,(G)n/2+1,由狄拉克定理：,n,阶图,G,有,H,圈,C.,又因,n,为偶数，所以,C,为偶圈。于是由,C,可得到,G,的两个,1,因子。设其中一个为,F,1,。,考虑,G,1,=G-F,1,。则,(G,1,)n/2,。于是,G,1,中有,H,圈,C,1,.,作,H=C,1,F,1,。显然,H,是,G,的一个,3,因子。,22,例,9,证明：一棵树,G,有完美匹配当且仅当对所有顶点,v,V(G),有：,o(G-v)=1,。,证明：“必要性”,一方面：若,G,有完美匹配，由托特定理：,O(G-v),1;,另一方面：若树,G,有完美匹配，则显然,G,为偶阶树，于是,O(G-v),1;,所以：,O(G-v),=1,。,“充分性”,由于对任意点,v,V(G),有,O(G-v),=1,。,23,设,C,v,是,G-v,的奇分支，又设,G,中由,v,连到,G-v,的奇分支的边为,vu,，显然，由,u,连到,G-u,的奇分支的边也是,uv,。,令,M=,e(v):,它是由,v,连到,G-v,的边，,v,V(G),则：,M,是,G,的完美匹配。,v,u,例,10,证明：每个,2k(k0),正则图是,2,可因子分解的。,24,证明：设,G,是,2k,连通正则图，,V(G)=,v,1,v,2,v,n,。则,G,存在欧拉环游,C,。,由,C,构造偶图,G,1,=(X,Y),如下：,X=,x,1,x,2,x,n,Y=,y,1,y,2,y,n,x,i,与,y,j,在,G,1,=(X,Y),中连线当且仅当,v,i,与,v,j,在,C,中顺次相连接。,显然偶图,G,1,=(X,Y),是一个,k,正则偶图。所以,G,1,可以,1,因子分解。,而,G,1,=(X,Y),的一个,1,因子对应于,G,中一个,2,因子。所以,G,可以,2,因子分解。,25,作业,P117-118,习题,4,：,3,4,5,，,6,，,7,，,8,，,9,26,Thank You!,