资源预览内容
第1页 / 共26页
第2页 / 共26页
第3页 / 共26页
第4页 / 共26页
第5页 / 共26页
第6页 / 共26页
第7页 / 共26页
第8页 / 共26页
第9页 / 共26页
第10页 / 共26页
亲,该文档总共26页,到这儿已超出免费预览范围,如果喜欢就下载吧!
资源描述
1图论及其应用应用数学学院2本次课主要内容(一)、图的一因子分解(二)、图的二因子分解(三)、图的森林因子分解图的因子分解3把一个图按照某种方式分解成若干边不重的子图之并有 重要意义。理论上,通过分解,可以深刻地揭示图的结构 特征;在应用上,网络通信中,当有多个信息传输时,往 往限制单个信息在某一子网中传递,这就涉及网络分解问 题。一个图分解方式是多种多样的。作为图分解的典型例子 ,我们介绍图的因子分解。所谓一个图G的因子Gi,是指至少包含G的一条边的生成 子图。所谓一个图G的因子分解,是指把图G分解为若干个边不 重的因子之并。所谓一个图G的n因子,是指图G的n度正则因子。4如果一个图G能够分解为若干n因子之并,称G是可n因 子分解的。图G1在上图中,红色边在G1中的导出子图,是G的一个一因 子;红色边在G2中的导出子图,是G的一个二因子。图G2研究图的因子分解主要是两个方面:一是能否进行分解( 因子分解的存在性),二是如何分解(分解算法).(一)、图的一因子分解5图的一个一因子实际上就是图的一个完美匹配。一个图 能够作一因子分解,也就是它能够分解为若干边不重的完 美匹配之并。定理1 K2n可一因子分解。证明:把K2n的2n个顶点编号为1,2,, 2n。作如下排 列: 2n132: :n2n-12n-2: :n+16图中,每行两点邻接,显然作 成K2n的一个一因子。2n132: :n2n-12n-2: :n+1然后按照图中箭头方向移动一 个位置,又可以得到K2n的一个一 因子,不断作下去,得到K2n的2n -1个边不重的一因子,其并恰好 为K2n。例1 将K4作一因子分解。1234 K44123123471234423143121234例2 证明:K4有唯一的一因子分解。证明:由习题5第一题知:K4只有3个不同的完美匹配。 而k4的每个1因子分解包含3个不同完美匹配,所以,其1 因子分解唯一。8例3 证明:K2n的一因子分解数目为:证明:由习题5第一题知:K2n的不同完美匹配的个数为(2n- 1)!。所以,K2n的以因子分解数目为(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的三个一因子为G1,G2,G3。不失 一般性,设割边e G1。显然,G-G2的每个分支必然为圈。所以e在G的某个 圈中,这与e是G的割边矛盾。注:没有割边的三正则图可能也没有一因子分解,如 彼得森图就是如此!尽管它存在完美匹配。(二)、图的二因子分解如果一个图可以分解为若干2度正则因子之并,称G 可以2因子分解。注意:G的一个H圈肯定是G的一个2因 子,但是G的一个2因子不一定是G的H圈。2因子可以不 连通。11例如,在下图中:两个红色圈的并构成图的一个2因子,但不是H圈。一个显然结论是:G能进行2因子分解,其顶点度数 必然为偶数。(注意,不一定是欧拉图)定理4 K2n+1可2因子分解。证明:设作路12其中,设Pi上的第j点为vk,则:下标取为1, 2, 2n (mod2n)生成圈Hi为v2n+1与Pi的两个端点连线。例4 对K7作2因子分解。解:v7v6v5v4v3v2v1v7v6v5v4v3v2v1v7v6v5v4v3v2v1v7v6v5v4v3v2v113定理5 K2n可分解为一个1因子和n-1个2因子之和。证明:设V(K2n)=v1,v2,v2n作n-1条路:脚标按模2n-1计算。然后把v2n和Pi的两个端点连接。例5 把K6分解为一个1因子和2个2因子分解。v6v5v4v3v2v114解:v6v5v4v3v2v1v6v5v4v3v2v1v6v5v4v3v2v1定理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例如:K5的一种森林因子分解为:主要讨论:图G分解为边不重的森林因子的最少数目问 题,称这个最少数目为G的荫度,记为(G)。纳什-威廉斯得到了图的荫度计算公式。17定理8 图G的荫度为:其中s是G的子图Hs的顶点数,而:例6 求(K5)和(K3,3).1819定理9拜内克给出了完全图和完全偶图的森林因子分解。对于K2n,将其分解为n条路Pi = vivi-1vi+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的最 后一个森林因子。20例7 对K7作最小森林因子分解。v7v6v5v4v3v2v1v3v7v6v5v4v2v1v7v6v5v4v3v2v1v7v6v5v4v3v2v121v7v6v5v4v3v2v1例8 证明:若n为偶数,且(G)n/2+1 ,则n阶图G有 3因子。证明:因(G)n/2+1 ,由狄拉克定理:n阶图G有H 圈C .又因n为偶数,所以C为偶圈。于是由C可得到G的 两个1因子。设其中一个为F1。考虑G1=G-F1。则(G1)n/2。于是G1中有H圈C1.作H=C1F1。显然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设Cv是G-v的奇分支,又设G中由v连到G-v的奇分支的 边为vu,显然,由u连到G-u的奇分支的边也是uv。令M=e(v):它是由v连到G-v的边,v V(G) 则:M是G的完美匹配。vu例10 证明:每个2k (k0)正则图是2可因子分解的。24证明:设G是2k连通正则图,V(G)=v1,v2,vn。 则G存在欧拉环游C。由C构造偶图G1=(X, Y)如下:X=x1,x2,xn, Y=y1,y2,ynxi与yj在G1=(X, Y)中连线当且仅当vi与vj在C中顺次相 连接。显然偶图G1=(X, Y)是一个k正则偶图。所以G1可以1 因子分解。而G1=(X, Y)的一个1因子对应于G中一个2因子。所以 G可以2因子分解。25作业P117-118 习题4 : 3, 4, 5,6,7,8,926Thank You !
收藏 下载该资源
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号