圖論課件圖的因子分解

1本次課主要內(nèi)容(一)、圖的一因子分解(二)、圖的二因子分解(三)、圖的森林因子分解圖的因子分解1本次課主要內(nèi)容(一)、圖的一因子分解(二)、圖的二因子分解12把一個(gè)圖按照某種方式分解成若干邊不重的子圖之并有重要意義。理論上，通過(guò)分解，可以深刻地揭示圖的結(jié)構(gòu)特征；在應(yīng)用上，網(wǎng)絡(luò)通信中，當(dāng)有多個(gè)信息傳輸時(shí)，往往限制單個(gè)信息在某一子網(wǎng)中傳遞，這就涉及網(wǎng)絡(luò)分解問(wèn)題。一個(gè)圖分解方式是多種多樣的。作為圖分解的典型例子，我們介紹圖的因子分解。所謂一個(gè)圖G的因子Gi，是指至少包含G的一條邊的生成子圖。所謂一個(gè)圖G的因子分解，是指把圖G分解為若干個(gè)邊不重的因子之并。所謂一個(gè)圖G的n因子，是指圖G的n度正則因子。2把一個(gè)圖按照某種方式分解成若干邊不重的子圖之并有23如果一個(gè)圖G能夠分解為若干n因子之并，稱G是可n因子分解的。圖G1在上圖中，紅色邊在G1中的導(dǎo)出子圖，是G的一個(gè)一因子；紅色邊在G2中的導(dǎo)出子圖，是G的一個(gè)二因子。圖G2研究圖的因子分解主要是兩個(gè)方面：一是能否進(jìn)行分解(因子分解的存在性),二是如何分解(分解算法).(一)、圖的一因子分解3如果一個(gè)圖G能夠分解為若干n因子之并，稱G是可n34圖的一個(gè)一因子實(shí)際上就是圖的一個(gè)完美匹配。一個(gè)圖能夠作一因子分解，也就是它能夠分解為若干邊不重的完美匹配之并。定理1K2n可一因子分解。證明：把K2n的2n個(gè)頂點(diǎn)編號(hào)為1，2，…,2n。作如下排列：2n132::n2n-12n-2::n+14圖的一個(gè)一因子實(shí)際上就是圖的一個(gè)完美匹配。一個(gè)圖45圖中，每行兩點(diǎn)鄰接，顯然作成K2n的一個(gè)一因子。2n132::n2n-12n-2::n+1然后按照?qǐng)D中箭頭方向移動(dòng)一個(gè)位置，又可以得到K2n的一個(gè)一因子，不斷作下去，得到K2n的2n-1個(gè)邊不重的一因子，其并恰好為K2n。例1將K4作一因子分解。1234K4→412312345圖中，每行兩點(diǎn)鄰接，顯然作成K2n的一個(gè)一因子。561234423143121234例2證明：K4有唯一的一因子分解。證明：由習(xí)題5第一題知：K4只有3個(gè)不同的完美匹配。而k4的每個(gè)1因子分解包含3個(gè)不同完美匹配，所以，其1因子分解唯一。61234423143121234例2證明：K467例3證明：K2n的一因子分解數(shù)目為：證明：由習(xí)題5第一題知：K2n的不同完美匹配的個(gè)數(shù)為(2n-1)!!。所以，K2n的以因子分解數(shù)目為(2n-1)!!個(gè)。即：例4證明：每個(gè)k(k>0)正則偶圖G是一可因子分解的。證明：因?yàn)槊總€(gè)k(k>0)正則偶圖G存在完美匹配，設(shè)Q是它的一個(gè)一因子，則G-Q還是正則偶圖，由歸納知，G可作一因子分解。7例3證明：K2n的一因子分解數(shù)目為：證明：由習(xí)78定理2具有H圈的三正則圖可一因子分解。證明：先從三正則圖G中抽取H圈，顯然剩下邊構(gòu)成G的一個(gè)一因子。而H圈顯然可以分解為兩個(gè)一因子。所以G可以分解為3個(gè)一因子。注：定理2的逆不一定成立。例如：上圖是三正則圖，且可以一因子分解，但不存在圈。8定理2具有H圈的三正則圖可一因子分解。89定理3若三正則圖有割邊，則它不能一因子分解。證明：若不然，設(shè)G的三個(gè)一因子為G1,G2,G3。不失一般性，設(shè)割邊e∈G1。顯然，G-G2的每個(gè)分支必然為圈。所以e在G的某個(gè)圈中，這與e是G的割邊矛盾。注：沒(méi)有割邊的三正則圖可能也沒(méi)有一因子分解，如彼得森圖就是如此！盡管它存在完美匹配。(二)、圖的二因子分解如果一個(gè)圖可以分解為若干2度正則因子之并，稱G可以2因子分解。注意：G的一個(gè)H圈肯定是G的一個(gè)2因子，但是G的一個(gè)2因子不一定是G的H圈。2因子可以不連通。9定理3若三正則圖有割邊，則它不能一因子分解。910例如，在下圖中：兩個(gè)紅色圈的并構(gòu)成圖的一個(gè)2因子，但不是H圈。一個(gè)顯然結(jié)論是：G能進(jìn)行2因子分解，其頂點(diǎn)度數(shù)必然為偶數(shù)。(注意，不一定是歐拉圖)定理4K2n+1可2因子分解。證明：設(shè)作路10例如，在下圖中：兩個(gè)紅色圈的并構(gòu)成圖1011其中，設(shè)Pi上的第j點(diǎn)為vk，則：下標(biāo)取為1,2,…,2n(mod2n)生成圈Hi為v2n+1與Pi的兩個(gè)端點(diǎn)連線。例4對(duì)K7作2因子分解。解：v7v6v5v4v3v2v1v7v6v5v4v3v2v1v7v6v5v4v3v2v1v7v6v5v4v3v2v111其中，設(shè)Pi上的第j點(diǎn)為vk，則：下1112定理5K2n可分解為一個(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因子和2個(gè)2因子分解。v6v5v4v3v2v112定理5K2n可分解為一個(gè)1因子和n-1個(gè)21213解：v6v5v4v3v2v1v6v5v4v3v2v1v6v5v4v3v2v1定理6每個(gè)沒(méi)有割邊的3正則圖是一個(gè)1因子和1個(gè)2因子之和。證明：因每個(gè)沒(méi)有割邊的3正則圖存在完美匹配M，顯然，G-M是2因子。13解：v6v5v4v3v2v1v6v5v4v3v1314定理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年彼得森證明過(guò)的一個(gè)結(jié)論：頂點(diǎn)度數(shù)為偶數(shù)的任意正則圖存在一個(gè)2因子Q。所以，G-Q是2k階正則圖。由歸納假設(shè)，充分性得證。(三)、圖的森林因子分解把一個(gè)圖分解為若干邊不重的森林因子的和，稱為圖的森林因子分解。14定理7一個(gè)連通圖可2因子分解當(dāng)且僅當(dāng)它是偶1415例如：K5的一種森林因子分解為：主要討論：圖G分解為邊不重的森林因子的最少數(shù)目問(wèn)題，稱這個(gè)最少數(shù)目為G的蔭度，記為σ(G)。納什---威廉斯得到了圖的蔭度計(jì)算公式。15例如：K5的一種森林因子分解為：主要1516定理8圖G的蔭度為：其中s是G的子圖Hs的頂點(diǎn)數(shù)，而：例6求σ(K5)和σ(K3,3).16定理8圖G的蔭度為：其中s是G的1617171718定理9拜內(nèi)克給出了完全圖和完全偶圖的森林因子分解。對(duì)于K2n，將其分解為n條路Pi=vivi-1vi+1vi-2vi+2…vi-nvi+n,腳標(biāo)按模2n計(jì)算。對(duì)于K2n+1，先作n條路Pi=vivi-1vi+1vi-2vi+2…vi-nvi+n,腳標(biāo)按模2n計(jì)算。在每條路外添上點(diǎn)v2n+1的n個(gè)森林因子；然后，v2n+1與v1,v2,…,v2n分別相連接得一星圖，這是G的最后一個(gè)森林因子。18定理9拜內(nèi)克給出了完全圖和完全偶圖的1819例7對(duì)K7作最小森林因子分解。v7v6v5v4v3v2v1v3v7v6v5v4v2v1v7v6v5v4v3v2v1v7v6v5v4v3v2v119例7對(duì)K7作最小森林因子分解。v7v6v5v1920v7v6v5v4v3v2v1例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=C1∪F1。顯然H是G的一個(gè)3因子。20v7v6v5v4v3v2v1例8證明：若n為2021例9證明：一棵樹G有完美匹配當(dāng)且僅當(dāng)對(duì)所有頂點(diǎn)v∈V(G),有：o(G-v)=1。證明：“必要性”一方面：若G有完美匹配，由托特定理：O(G-v)≦1;另一方面：若樹G有完美匹配，則顯然G為偶階樹，于是O(G-v)≥1;所以：O(G-v)=1?！俺浞中浴庇捎趯?duì)任意點(diǎn)v∈V(G),有O(G-v)=1。21例9證明：一棵樹G有完美匹配當(dāng)且僅當(dāng)對(duì)所有頂2122設(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證明：每個(gè)2k(k>0)正則圖是2可因子分解的。22設(shè)Cv是G-v的奇分支，又設(shè)G中由v連到G-v2223證明：設(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中順次相連接。顯然