圖論及其應用(17)

1、1本次課主要內(nèi)容本次課主要內(nèi)容(一一)、圖的一因子分解、圖的一因子分解(二二)、圖的二因子分解、圖的二因子分解(三三)、圖的森林因子分解、圖的森林因子分解圖的因子分解圖的因子分解2 把一個圖按照某種方式分解成若干邊不重的子圖之并有把一個圖按照某種方式分解成若干邊不重的子圖之并有重要意義。理論上，通過分解，可以深刻地揭示圖的結(jié)構(gòu)重要意義。理論上，通過分解，可以深刻地揭示圖的結(jié)構(gòu)特征；在應用上，網(wǎng)絡通信中，當有多個信息傳輸時，往特征；在應用上，網(wǎng)絡通信中，當有多個信息傳輸時，往往限制單個信息在某一子網(wǎng)中傳遞，這就涉及網(wǎng)絡分解問往限制單個信息在某一子網(wǎng)中傳遞，這就涉及網(wǎng)絡分解問題。題。 一個圖分解方

2、式是多種多樣的。作為圖分解的典型例子，一個圖分解方式是多種多樣的。作為圖分解的典型例子，我們介紹圖的因子分解。我們介紹圖的因子分解。 所謂一個圖所謂一個圖G的因子的因子Gi，是指至少包含，是指至少包含G的一條邊的生成的一條邊的生成子圖。子圖。 所謂一個圖所謂一個圖G的因子分解，是指把圖的因子分解，是指把圖G分解為若干個邊不分解為若干個邊不重的因子之并。重的因子之并。 所謂一個圖所謂一個圖G的的n因子，是指圖因子，是指圖G的的n度正則因子。度正則因子。3 如果一個圖如果一個圖G能夠分解為若干能夠分解為若干n因子之并，稱因子之并，稱G是可是可n因因子分解的。子分解的。圖圖G1 在上圖中，紅色邊在在

3、上圖中，紅色邊在G1中的導出子圖，是中的導出子圖，是G的一個一因的一個一因子；紅色邊在子；紅色邊在G2中的導出子圖，是中的導出子圖，是G的一個二因子。的一個二因子。圖圖G2 研究圖的因子分解主要是兩個方面：一是能否進行分解研究圖的因子分解主要是兩個方面：一是能否進行分解(因子分解的存在性因子分解的存在性),二是如何分解二是如何分解(分解算法分解算法).(一一)、圖的一因子分解、圖的一因子分解4 圖的一個一因子實際上就是圖的一個完美匹配。一個圖圖的一個一因子實際上就是圖的一個完美匹配。一個圖能夠作一因子分解，也就是它能夠分解為若干邊不重的完能夠作一因子分解，也就是它能夠分解為若干邊不重的完美匹配

4、之并。美匹配之并。 定理定理1 K2n可一因子分解?？梢灰蜃臃纸?。 證明：把證明：把K2n的的2n個頂點編號為個頂點編號為1，2，, 2n。作如下排。作如下排列：列：2n132:n2n-12n-2:n+15 圖中，每行兩點鄰接，顯然作圖中，每行兩點鄰接，顯然作成成K2n的一個一因子。的一個一因子。2n132:n2n-12n-2:n+1 然后按照圖中箭頭方向移動一然后按照圖中箭頭方向移動一個位置，又可以得到個位置，又可以得到K2n的一個一的一個一因子，不斷作下去，得到因子，不斷作下去，得到K2n的的2n-1個邊不重的一因子，其并恰個邊不重的一因子，其并恰好為好為K2n。 例例1 將將K4作一因子

5、分解。作一因子分解。1234K44123123461234423143121234 例例2 證明：證明：K4有唯一的一因子分解。有唯一的一因子分解。證明：由習題證明：由習題5第一題知：第一題知：K4只有只有3個不同的完美匹配。個不同的完美匹配。而而k4的每個的每個1因子分解包含因子分解包含3個不同完美匹配，所以，其個不同完美匹配，所以，其1因子分解唯一。因子分解唯一。7 例例3 證明：證明：K2n的一因子分解數(shù)目為：的一因子分解數(shù)目為：證明：由習題證明：由習題5第一題知：第一題知：K2n的不同完美匹配的個數(shù)為的不同完美匹配的個數(shù)為(2n-1)!。所以，。所以，K2n的以因子分解數(shù)目為的以因子分

6、解數(shù)目為(2n-1)!個。即：個。即：(2 )!2!nnn(2 )!(21)!2!nnnn 例例4 證明：每個證明：每個k (k0)正則偶圖正則偶圖G是一可因子分解的。是一可因子分解的。 證明：因為每個證明：因為每個k (k0)正則偶圖正則偶圖G存在完美匹配，設(shè)存在完美匹配，設(shè)Q是它的一個一因子，則是它的一個一因子，則G-Q還是正則偶圖，由歸納知，還是正則偶圖，由歸納知，G可作一因子分解?？勺饕灰蜃臃纸狻? 定理定理2 具有具有H圈的三正則圖可一因子分解。圈的三正則圖可一因子分解。 證明：先從三正則圖證明：先從三正則圖G中抽取中抽取H圈，顯然剩下邊構(gòu)成圈，顯然剩下邊構(gòu)成G的一個一因子。而的一個

7、一因子。而H圈顯然可以分解為兩個一因子。圈顯然可以分解為兩個一因子。所以所以G可以分解為可以分解為3個一因子。個一因子。 注：定理注：定理2的逆不一定成立。例如：的逆不一定成立。例如： 上圖是三正則圖，且可以一因子分解，但不存在圈。上圖是三正則圖，且可以一因子分解，但不存在圈。9 定理定理3 若三正則圖有割邊，則它不能一因子分解。若三正則圖有割邊，則它不能一因子分解。 證明：若不然，設(shè)證明：若不然，設(shè)G的三個一因子為的三個一因子為G1,G2,G3。不失。不失一般性，設(shè)割邊一般性，設(shè)割邊e G1。 顯然，顯然，G-G2的每個分支必然為圈。所以的每個分支必然為圈。所以e在在G的某個的某個圈中，這與

8、圈中，這與e是是G的割邊矛盾。的割邊矛盾。 注：沒有割邊的三正則圖可能也沒有一因子分解，如注：沒有割邊的三正則圖可能也沒有一因子分解，如彼得森圖就是如此！盡管它存在完美匹配。彼得森圖就是如此！盡管它存在完美匹配。(二二)、圖的二因子分解、圖的二因子分解 如果一個圖可以分解為若干如果一個圖可以分解為若干2度正則因子之并，稱度正則因子之并，稱G可以可以2因子分解。注意：因子分解。注意：G的一個的一個H圈肯定是圈肯定是G的一個的一個2因子，但是因子，但是G的一個的一個2因子不一定是因子不一定是G的的H圈。圈。2因子可因子可以不連通。以不連通。10 例如，在下圖中：例如，在下圖中： 兩個紅色圈的并構(gòu)成

9、圖的一個兩個紅色圈的并構(gòu)成圖的一個2因子，但不是因子，但不是H圈。圈。 一個顯然結(jié)論是：一個顯然結(jié)論是：G能進行能進行2因子分解，其頂點度數(shù)因子分解，其頂點度數(shù)必然為偶數(shù)。必然為偶數(shù)。(注意，不一定是歐拉圖注意，不一定是歐拉圖) 定理定理4 K2n+1可可2因子分解。因子分解。 證明：設(shè)證明：設(shè)211221(),nnV Kv vv 作路作路11223iiiiiiiininPv vvvvvvv11 其中，設(shè)其中，設(shè)Pi上的第上的第j點為點為vk，則：，則： 下標取為下標取為1, 2, 2n (mod2n)1(1)2jjki 生成圈生成圈Hi為為v2n+1與與Pi的兩個端點連線。的兩個端點連線。

10、例例4 對對K7作作2因子分解。因子分解。 解：解：1162534Pv v v v v vv7v6v5v4v3v2v12213645Pv v v v v v3324156Pv v v v v vv7v6v5v4v3v2v1v7v6v5v4v3v2v1v7v6v5v4v3v2v112 定理定理5 K2n可分解為一個可分解為一個1因子和因子和n-1個個2因子之和。因子之和。 證明：設(shè)證明：設(shè)V(K2n)=v1,v2,v2n 作作n-1條路：條路：1122311iiiiiiiininPv vvvvvvv 腳標按模腳標按模2n-1計算。然后把計算。然后把v2n和和Pi的兩個端點連接。的兩個端點連接。

11、例例5 把把K6分解為一個分解為一個1因子和因子和2個個2因子分解。因子分解。v6v5v4v3v2v113 解：解：v6v5v4v3v2v1115243Pv v v v v221354Pv v v v vv6v5v4v3v2v1v6v5v4v3v2v1 定理定理6 每個沒有割邊的每個沒有割邊的3正則圖是一個正則圖是一個1因子和因子和1個個2因因子之和。子之和。 證明：證明： 因每個沒有割邊的因每個沒有割邊的3正則圖存在完美匹配正則圖存在完美匹配M，顯，顯然，然，G-M是是2因子。因子。14 定理定理7 一個連通圖可一個連通圖可2因子分解當且僅當它是偶數(shù)度因子分解當且僅當它是偶數(shù)度正則圖。正則圖

12、。 證明：證明： 必要性顯然。必要性顯然。 充分性：當充分性：當G是是n階階2正則圖時，正則圖時，G本身是一個本身是一個2因子。因子。 設(shè)當設(shè)當G是是n階階2k正則圖時，可以進行正則圖時，可以進行2因子分解。當因子分解。當G是是n階階2k+2正則圖時，由正則圖時，由1891年彼得森證明過的一個結(jié)論：頂年彼得森證明過的一個結(jié)論：頂點度數(shù)為偶數(shù)的任意正則圖存在一個點度數(shù)為偶數(shù)的任意正則圖存在一個2因子因子Q。所以，。所以，G-Q是是2k階正則圖。由歸納假設(shè)，充分性得證。階正則圖。由歸納假設(shè)，充分性得證。(三三)、圖的森林因子分解、圖的森林因子分解 把一個圖分解為若干邊不重的森林因子的和，稱為圖的把

13、一個圖分解為若干邊不重的森林因子的和，稱為圖的森林因子分解。森林因子分解。15 例如：例如：K5的一種森林因子分解為：的一種森林因子分解為： 主要討論：圖主要討論：圖G分解為邊不重的森林因子的最少數(shù)目問分解為邊不重的森林因子的最少數(shù)目問題，稱這個最少數(shù)目為題，稱這個最少數(shù)目為G的蔭度，記為的蔭度，記為(G)(G)。 納什納什-威廉斯得到了圖的蔭度計算公式。威廉斯得到了圖的蔭度計算公式。16 定理定理8 圖圖G的蔭度為：的蔭度為：()max1ssmGs 其中其中s是是G的子圖的子圖Hs的頂點數(shù)，而：的頂點數(shù)，而：max()sssmE H 例例6 求求(K(K5 5) )和和(K3,3).2111

14、ssmsms3321ssmsms4621ssmsms51031ssmsms()3G172111ssmsms3211ssmsms4421ssmsms5621ssmsms3,3()3K6921ssmsms18 定理定理9()2nnK,()1r srsKrs 拜內(nèi)克給出了完全圖和完全偶圖的森林因子分解。拜內(nèi)克給出了完全圖和完全偶圖的森林因子分解。 對于對于K2n，將其分解為，將其分解為n條路條路Pi = vivi-1vi+1vi-2vi+2vi-nvi+n,腳腳標按模標按模2n計算。計算。 對于對于K2n+1，先作，先作n條路條路Pi = vivi-1vi+1vi-2vi+2vi-nvi+n,腳標按

15、腳標按模模2n計算。在每條路外添上點計算。在每條路外添上點v2n+1的的n個森林因子；個森林因子； 然后，然后，v2n+1與與v1,v2,v2n分別相連接得一星圖，這是分別相連接得一星圖，這是G的最的最后一個森林因子。后一個森林因子。19 例例7 對對K7作最小森林因子分解。作最小森林因子分解。v7v6v5v4v3v2v11162534Pv v v v v v2213645Pv v v v v v3324156Pv v v v v vv3v7v6v5v4v2v1v7v6v5v4v3v2v1v7v6v5v4v3v2v120v7v6v5v4v3v2v1 例例8 證明：若證明：若n為偶數(shù)，且為偶數(shù)，

16、且(G)n/2+1(G)n/2+1 ,則則n階圖階圖G有有3因子。因子。 證明：因證明：因(G)n/2+1(G)n/2+1 ,由狄拉克定理：由狄拉克定理：n階圖階圖G有有H圈圈C .又因又因n為偶數(shù)，所以為偶數(shù)，所以C為偶圈。于是由為偶圈。于是由C可得到可得到G的的兩個兩個1因子。設(shè)其中一個為因子。設(shè)其中一個為F1。 考慮考慮G1=G-F1。則。則(G1)n/2。于是。于是G1中有中有H圈圈C1. 作作H=C1F1。顯然。顯然H是是G的一個的一個3因子。因子。21 例例9 證明：一棵樹證明：一棵樹G有完美匹配當且僅當對所有頂點有完美匹配當且僅當對所有頂點v V(G),有：有：o(G-v)=1。

17、 證明：證明：“必要性必要性” 一方面：若一方面：若G有完美匹配，由托特定理：有完美匹配，由托特定理：O(G-v)1;1; 另一方面：若樹另一方面：若樹G有完美匹配，則顯然有完美匹配，則顯然G為偶階樹，于是為偶階樹，于是O(G-v)1;1; 所以：所以：O(G-v)=1=1。 “充分性充分性” 由于對任意點由于對任意點v V(G), 有有O(G-v)=1=1。22 設(shè)設(shè)Cv是是G-v的奇分支，又設(shè)的奇分支，又設(shè)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可因子分解的?？梢蜃臃纸獾?。23 證明：設(shè)證明：設(shè)G是是2k連通正則圖，連通正則圖，V(G)=v1,v2,vn。