ppt18圖的因子分解.ppt

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

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

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

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

5、，但是G的一個2因子不一定是G的H圈。2因子可以不連通。,11,例如，在下圖中：,兩個紅色圈的并構(gòu)成圖的一個2因子，但不是H圈。,一個顯然結(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的兩個端點(diǎn)連線。,例4 對K7作2因子分解。,解：,13,定理5 K2n可分解為一個1因子和n-1個2因子之和。,證明：設(shè)V(K2n)=v1,v2,v2n,作n-1條路：,腳標(biāo)按模2n-1計算。然后把v2n和Pi的兩個端點(diǎn)連接。,例5 把K6分解為一個1因子和

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

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

8、；,然后，v2n+1與v1,v2,v2n分別相連接得一星圖，這是G的最后一個森林因子。,20,例7 對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的兩個1因子。設(shè)其中一個為F1。,考慮G1=G-F1。則(G1)n/2。于是G1中有H圈C1.,作H=C1F1。顯然H是G的一個3因子。,22,例9 證明：一棵樹G有完美匹配當(dāng)且僅當(dāng)對所有頂點(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。,“充分性”,由于對任意點(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 證明：每個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中順次相連接。,顯然偶