圖論圖的因子分解

圖論課件圖的因子分解第一頁，共二十六頁，2022年，8月28日2本次課主要內(nèi)容(一)、圖的一因子分解(二)、圖的二因子分解(三)、圖的森林因子分解圖的因子分解第二頁，共二十六頁，2022年，8月28日3把一個圖按照某種方式分解成若干邊不重的子圖之并有重要意義。理論上，通過分解，可以深刻地揭示圖的結(jié)構(gòu)特征；在應用上，網(wǎng)絡通信中，當有多個信息傳輸時，往往限制單個信息在某一子網(wǎng)中傳遞，這就涉及網(wǎng)絡分解問題。一個圖分解方式是多種多樣的。作為圖分解的典型例子，我們介紹圖的因子分解。所謂一個圖G的因子Gi，是指至少包含G的一條邊的生成子圖。所謂一個圖G的因子分解，是指把圖G分解為若干個邊不重的因子之并。所謂一個圖G的n因子，是指圖G的n度正則因子。第三頁，共二十六頁，2022年，8月28日4如果一個圖G能夠分解為若干n因子之并，稱G是可n因子分解的。圖G1在上圖中，紅色邊在G1中的導出子圖，是G的一個一因子；紅色邊在G2中的導出子圖，是G的一個二因子。圖G2研究圖的因子分解主要是兩個方面：一是能否進行分解(因子分解的存在性),二是如何分解(分解算法).(一)、圖的一因子分解第四頁，共二十六頁，2022年，8月28日5圖的一個一因子實際上就是圖的一個完美匹配。一個圖能夠作一因子分解，也就是它能夠分解為若干邊不重的完美匹配之并。定理1K2n可一因子分解。證明：把K2n的2n個頂點編號為1，2，…,2n。作如下排列：2n132::n2n-12n-2::n+1第五頁，共二十六頁，2022年，8月28日6圖中，每行兩點鄰接，顯然作成K2n的一個一因子。2n132::n2n-12n-2::n+1然后按照圖中箭頭方向移動一個位置，又可以得到K2n的一個一因子，不斷作下去，得到K2n的2n-1個邊不重的一因子，其并恰好為K2n。例1將K4作一因子分解。1234K4→41231234第六頁，共二十六頁，2022年，8月28日71234423143121234例2證明：K4有唯一的一因子分解。證明：由習題5第一題知：K4只有3個不同的完美匹配。而k4的每個1因子分解包含3個不同完美匹配，所以，其1因子分解唯一。第七頁，共二十六頁，2022年，8月28日8例3證明：K2n的一因子分解數(shù)目為：證明：由習題5第一題知：K2n的不同完美匹配的個數(shù)為(2n-1)!!。所以，K2n的以因子分解數(shù)目為(2n-1)!!個。即：例4證明：每個k(k>0)正則偶圖G是一可因子分解的。證明：因為每個k(k>0)正則偶圖G存在完美匹配，設(shè)Q是它的一個一因子，則G-Q還是正則偶圖，由歸納知，G可作一因子分解。第八頁，共二十六頁，2022年，8月28日9定理2具有H圈的三正則圖可一因子分解。證明：先從三正則圖G中抽取H圈，顯然剩下邊構(gòu)成G的一個一因子。而H圈顯然可以分解為兩個一因子。所以G可以分解為3個一因子。注：定理2的逆不一定成立。例如：上圖是三正則圖，且可以一因子分解，但不存在圈。第九頁，共二十六頁，2022年，8月28日10定理3若三正則圖有割邊，則它不能一因子分解。證明：若不然，設(shè)G的三個一因子為G1,G2,G3。不失一般性，設(shè)割邊e∈G1。顯然，G-G2的每個分支必然為圈。所以e在G的某個圈中，這與e是G的割邊矛盾。注：沒有割邊的三正則圖可能也沒有一因子分解，如彼得森圖就是如此！盡管它存在完美匹配。(二)、圖的二因子分解如果一個圖可以分解為若干2度正則因子之并，稱G可以2因子分解。注意：G的一個H圈肯定是G的一個2因子，但是G的一個2因子不一定是G的H圈。2因子可以不連通。第十頁，共二十六頁，2022年，8月28日11例如，在下圖中：兩個紅色圈的并構(gòu)成圖的一個2因子，但不是H圈。一個顯然結(jié)論是：G能進行2因子分解，其頂點度數(shù)必然為偶數(shù)。(注意，不一定是歐拉圖)定理4K2n+1可2因子分解。證明：設(shè)作路第十一頁，共二十六頁，2022年，8月28日12其中，設(shè)Pi上的第j點為vk，則：下標取為1,2,…,2n(mod2n)生成圈Hi為v2n+1與Pi的兩個端點連線。例4對K7作2因子分解。解：v7v6v5v4v3v2v1v7v6v5v4v3v2v1v7v6v5v4v3v2v1v7v6v5v4v3v2v1第十二頁，共二十六頁，2022年，8月28日13定理5K2n可分解為一個1因子和n-1個2因子之和。證明：設(shè)V(K2n)=｛v1,v2,…,v2n｝作n-1條路：腳標按模2n-1計算。然后把v2n和Pi的兩個端點連接。例5把K6分解為一個1因子和2個2因子分解。v6v5v4v3v2v1第十三頁，共二十六頁，2022年，8月28日14解：v6v5v4v3v2v1v6v5v4v3v2v1v6v5v4v3v2v1定理6每個沒有割邊的3正則圖是一個1因子和1個2因子之和。證明：

因每個沒有割邊的3正則圖存在完美匹配M，顯然，G-M是2因子。第十四頁，共二十六頁，2022年，8月28日15定理7一個連通圖可2因子分解當且僅當它是偶數(shù)度正則圖。證明：

必要性顯然。充分性：當G是n階2正則圖時，G本身是一個2因子。設(shè)當G是n階2k正則圖時，可以進行2因子分解。當G是n階2k+2正則圖時，由1891年彼得森證明過的一個結(jié)論：頂點度數(shù)為偶數(shù)的任意正則圖存在一個2因子Q。所以，G-Q是2k階正則圖。由歸納假設(shè)，充分性得證。(三)、圖的森林因子分解把一個圖分解為若干邊不重的森林因子的和，稱為圖的森林因子分解。第十五頁，共二十六頁，2022年，8月28日16例如：K5的一種森林因子分解為：主要討論：圖G分解為邊不重的森林因子的最少數(shù)目問題，稱這個最少數(shù)目為G的蔭度，記為σ(G)。納什---威廉斯得到了圖的蔭度計算公式。第十六頁，共二十六頁，2022年，8月28日17定理8圖G的蔭度為：其中s是G的子圖Hs的頂點數(shù)，而：例6求σ(K5)和σ(K3,3).第十七頁，共二十六頁，2022年，8月28日18第十八頁，共二十六頁，2022年，8月28日19定理9拜內(nèi)克給出了完全圖和完全偶圖的森林因子分解。對于K2n，將其分解為n條路Pi=vivi-1vi+1vi-2vi+2…vi-nvi+n,腳標按模2n計算。對于K2n+1，先作n條路Pi=vivi-1vi+1vi-2vi+2…vi-nvi+n,腳標按模2n計算。在每條路外添上點v2n+1的n個森林因子；然后，v2n+1與v1,v2,…,v2n分別相連接得一星圖，這是G的最后一個森林因子。第十九頁，共二十六頁，2022年，8月28日20例7對K7作最小森林因子分解。v7v6v5v4v3v2v1v3v7v6v5v4v2v1v7v6v5v4v3v2v1v7v6v5v4v3v2v1第二十頁，共二十六頁，2022年，8月28日21v7v6v5v4v3v2v1例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=C1∪F1。顯然H是G的一個3因子。第二十一頁，共二十六頁，2022年，8月28日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?！俺浞中浴庇捎趯θ我恻cv∈V(G),有O(G-v)=1。第二十二頁，共二十六頁，2022年，8月28日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的完美匹配。vu例10證明：每個2k(k>0)正則圖是2可因子分解的。第二十三頁，共二十六頁，2022年，8月28日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)中連線當且僅當vi與vj在C中順次相連接。