ppt18圖的因子分解.ppt

1、1,Email: ,圖論及其應(yīng)用,任課教師：楊春,數(shù)學(xué)科學(xué)學(xué)院,2,本次課主要內(nèi)容,(一)、圖的一因子分解,(二)、圖的二因子分解,(三)、圖的森林因子分解,圖的因子分解,3,把一個(gè)圖按照某種方式分解成若干邊不重的子圖之并有重要意義。理論上，通過分解，可以深刻地揭示圖的結(jié)構(gòu)特征；在應(yīng)用上，網(wǎng)絡(luò)通信中，當(dāng)有多個(gè)信息傳輸時(shí)，往往限制單個(gè)信息在某一子網(wǎng)中傳遞，這就涉及網(wǎng)絡(luò)分解問題。,一個(gè)圖分解方式是多種多樣的。作為圖分解的典型例子，我們介紹圖的因子分解。,所謂一個(gè)圖G的因子Gi，是指至少包含G的一條邊的生成子圖。,所謂一個(gè)圖G的因子分解，是指把圖G分解為若干個(gè)邊不重的因子之并。,所謂一個(gè)圖G的n因子

2、，是指圖G的n度正則因子。,4,如果一個(gè)圖G能夠分解為若干n因子之并，稱G是可n因子分解的。,在上圖中，紅色邊在G1中的導(dǎo)出子圖，是G的一個(gè)一因子；紅色邊在G2中的導(dǎo)出子圖，是G的一個(gè)二因子。,研究圖的因子分解主要是兩個(gè)方面：一是能否進(jìn)行分解(因子分解的存在性),二是如何分解(分解算法).,(一)、圖的一因子分解,5,圖的一個(gè)一因子實(shí)際上就是圖的一個(gè)完美匹配的導(dǎo)出子圖。一個(gè)圖能夠作一因子分解，也就是它能夠分解為若干邊不重的完美匹配的導(dǎo)出子圖之并。,定理1 K2n可一因子分解。,證明：把K2n的2n個(gè)頂點(diǎn)編號(hào)為1，2，, 2n。作如下排列：,6,圖中，每行兩點(diǎn)鄰接，顯然作成K2n的一個(gè)一因子。,

3、然后按照?qǐng)D中箭頭方向移動(dòng)一個(gè)位置，又可以得到K2n的一個(gè)一因子，不斷作下去，得到K2n的2n-1個(gè)邊不重的一因子，其并恰好為K2n。,例1 將K4作一因子分解。,7,例2 證明：K4有唯一的一因子分解。,證明：由習(xí)題5第一題知：K4只有3個(gè)不同的完美匹配。而k4的每個(gè)1因子分解包含3個(gè)不同完美匹配，所以，其1因子分解唯一。,8,例3 證明：每個(gè)k (k0)正則偶圖G是一可因子分解的。,證明：因?yàn)槊總€(gè)k (k0)正則偶圖G存在完美匹配，設(shè)Q是它的一個(gè)一因子，則G-Q還是正則偶圖，由歸納知，G可作一因子分解。,9,定理2 具有H圈的三正則圖可一因子分解。,證明：先從三正則圖G中抽取H圈，顯然剩下邊

4、構(gòu)成G的一個(gè)一因子。而H圈是偶圈，它顯然可以分解為兩個(gè)一因子。所以G可以分解為3個(gè)一因子。,注：定理2的逆不一定成立。例如：,上圖是三正則圖，且可以一因子分解，但不存在H圈。,10,定理3 若三正則圖有割邊，則它不能一因子分解。,證明：若不然，設(shè)G的三個(gè)一因子為G1,G2,G3。不失一般性，設(shè)割邊e G1。,顯然，G-G2的每個(gè)分支必然為圈。所以e在G的某個(gè)圈中，這與e是G的割邊矛盾。,注：沒有割邊的三正則圖可能也沒有一因子分解，如彼得森圖就是如此！盡管它存在完美匹配。,(二)、圖的二因子分解,如果一個(gè)圖可以分解為若干2度正則因子之并，稱G可以2因子分解。注意：G的一個(gè)H圈肯定是G的一個(gè)2因子

5、，但是G的一個(gè)2因子不一定是G的H圈。2因子可以不連通。,11,例如，在下圖中：,兩個(gè)紅色圈的并構(gòu)成圖的一個(gè)2因子，但不是H圈。,一個(gè)顯然結(jié)論是：G能進(jìn)行2因子分解，其頂點(diǎn)度數(shù)必然為偶數(shù)。(注意，不一定是歐拉圖),定理4 K2n+1可2因子分解。,證明：設(shè),作路,12,下標(biāo)取為1, 2, 2n (mod2n),生成圈Hi為v2n+1與Pi的兩個(gè)端點(diǎn)連線。,例4 對(duì)K7作2因子分解。,解：,13,定理5 K2n可分解為一個(gè)1因子和n-1個(gè)2因子之和。,證明：設(shè)V(K2n)=v1,v2,v2n,作n-1條路：,腳標(biāo)按模2n-1計(jì)算。然后把v2n和Pi的兩個(gè)端點(diǎn)連接。,例5 把K6分解為一個(gè)1因子和

6、2個(gè)2因子分解。,14,解：,定理6 每個(gè)沒有割邊的3正則圖是一個(gè)1因子和1個(gè)2因子之和。,證明： 因每個(gè)沒有割邊的3正則圖存在完美匹配M，顯然，G-M是2因子。,15,定理7 一個(gè)連通圖可2因子分解當(dāng)且僅當(dāng)它是偶數(shù)度正則圖。,證明： 必要性顯然。,充分性：當(dāng)G是n階2正則圖時(shí)，G本身是一個(gè)2因子。,設(shè)當(dāng)G是n階2k正則圖時(shí)，可以進(jìn)行2因子分解。當(dāng)G是n階2k+2正則圖時(shí)，由1891年彼得森證明過的一個(gè)結(jié)論：頂點(diǎn)度數(shù)為偶數(shù)的任意正則圖存在一個(gè)2因子Q。所以，G-Q是2k階正則圖。由歸納假設(shè)，充分性得證。,(三)、圖的森林因子分解,把一個(gè)圖分解為若干邊不重的森林因子的和，稱為圖的森林因子分解。,

7、16,例如：K5的一種森林因子分解為：,主要討論：圖G分解為邊不重的森林因子的最少數(shù)目問題，稱這個(gè)最少數(shù)目為G的蔭度，記為(G)。,納什-威廉斯得到了圖的蔭度計(jì)算公式。,17,定理8 圖G的蔭度為：,其中s是G的子圖Hs的頂點(diǎn)數(shù)，而：,例6 求(K5)和(K3,3).,18,19,定理9,拜內(nèi)克給出了完全圖和完全偶圖的最小森林因子分解。,對(duì)于K2n，將其分解為n條路Pi = vivi-1vi+1vi-2vi+2vi-nvi+n,腳標(biāo)按模2n計(jì)算。,對(duì)于K2n+1，先作n條路Pi = vivi-1vi+1vi-2vi+2vi-nvi+n,腳標(biāo)按模2n計(jì)算。在每條路外添上點(diǎn)v2n+1的n個(gè)森林因子

8、；,然后，v2n+1與v1,v2,v2n分別相連接得一星圖，這是G的最后一個(gè)森林因子。,20,例7 對(duì)K7作最小森林因子分解。,21,例8 證明：若n為偶數(shù)，且(G)n/2+1 ,則n階圖G有3因子。,證明：因(G)n/2+1 ,由狄拉克定理：n階圖G有H圈C .又因n為偶數(shù)，所以C為偶圈。于是由C可得到G的兩個(gè)1因子。設(shè)其中一個(gè)為F1。,考慮G1=G-F1。則(G1)n/2。于是G1中有H圈C1.,作H=C1F1。顯然H是G的一個(gè)3因子。,22,例9 證明：一棵樹G有完美匹配當(dāng)且僅當(dāng)對(duì)所有頂點(diǎn)v V(G),有：o (G - v)=1。,證明：“必要性”,一方面：若G有完美匹配，由托特定理：O

9、(G-v)1;,另一方面：若樹G有完美匹配，則顯然G為偶階樹，于是o(G-v)1;,所以：o(G-v)=1。,“充分性”,由于對(duì)任意點(diǎn)v V(G), 有o(G-v)=1。,23,設(shè)Cv是G-v的奇分支，又設(shè)G中由v連到G-v的奇分支的邊為vu，顯然，由u連到G-u的奇分支的邊也是uv。,令M=e(v):它是由v連到G-v的奇分支的邊，v V(G) ,則：M是G的完美匹配。,例10 證明：每個(gè)2k (k0)正則圖是2可因子分解的。,24,證明：設(shè)G是2k正則連通圖，V(G)=v1,v2,vn。則G存在歐拉環(huán)游C。,由C構(gòu)造偶圖G1=(X, Y)如下：,X=x1,x2,xn, Y=y1,y2,yn,xi與yj在G1=(X, Y)中連線當(dāng)且僅當(dāng)vi與vj在C中順次相連接。,顯然偶