【正文】 G的割邊矛盾。 注：沒有割邊的三正則圖可能也沒有一因子分解，如彼得森圖就是如此！盡管它存在完美匹配。 (二 )、圖的二因子分解 如果一個圖可以分解為若干 2度正則因子之并，稱 G可以 2因子分解。注意： G的一個 H圈肯定是 G的一個 2因子，但是 G的一個 2因子不一定是 G的 H圈。 2因子可以不連通。 例如，在下圖中： 兩個紅色圈的并構成圖的一個 2因子，但不是 H圈。 一個顯然結論是： G能進行 2因子分解，其頂點度數(shù)必然為偶數(shù)。 (注意，不一定是歐拉圖 ) 定理 4 K2n+1可 2因子分解。 證明：設 ? ?2 1 1 2 2 1( ) , , ,nnV K v v v??? 作路 1 1 2 2 3i i i i i i i i n i nP v v v v v v v v? ? ? ? ? ? ?? 其中，設 Pi上的第 j點為 vk，則： 下標取為 1, 2,…, 2n (mod2n) 1( 1 ) 2j jki ? ??? ? ? ???? 生成圈 Hi為 v2n+1與 Pi的兩個端點連線。 例 4 對 K7作 2因子分解。 解： 1 1 6 2 5 3 4P v v v v v v?v7 v6 v5 v4 v3 v2 v1 2 2 1 3 6 4 5P v v v v v v?3 3 2 4 1 5 6P v v v v v v?v7 v6 v5 v4 v3 v2 v1 v7 v6 v5 v4 v3 v2 v1 v7 v6 v5 v4 v3 v2 v1 定理 5 K2n可分解為一個 1因子和 n1個 2因子之和。 證明：設 V(K2n)=｛ v1,v2,…,v 2n｝ 作 n1條路： 1 1 2 2 3 1 1i i i i i i i i n i nP v v v v v v v v? ? ? ? ? ? ? ? ?? 腳標按模 2n1計算。然后把 v2n和 Pi的兩個端點連接。 例 5 把 K6分解為一個 1因子和 2個 2因子分解。 v6 v5 v4 v3 v2 v1 解： v6 v5 v4 v3 v2 v1 1 1 5 2 4 3P v v v v v? 2 2 1 3 5 4P v v v v v?v6 v5 v4 v3 v2 v1 v6 v5 v4 v3 v2 v1 定理 6 每個沒有割邊的 3正則圖是一個 1因子和 1個 2因子之和。 證明： 因每個沒有割邊的 3正則圖存在完美匹配 M，顯然， GM是 2因子。 定理 7 一個連通圖可 2因子分解當且僅當它是偶數(shù)度正則圖。 證明： 必要性顯然。 充分性：當 G是 n階 2正則圖時， G本身是一個 2因子。 設當 G是 n階 2k正則圖時，可以進行 2因子分解。當 G是 n階 2k+2正則圖時，由 1891年彼得森證明過的一個結論：頂點度數(shù)為偶數(shù)的任意正則圖存在一個 2因子 Q。所以， GQ是 2k階正則圖。由歸納假設，充分性得證。 (三 )、圖的森林因子分解 把一個圖分解為若干邊不重的森林因子的和，稱為圖的森林因子分解。 例如： K5的一種森林因子分解為： 主要討論：圖 G分解為邊不重的森林因子的最少數(shù)目問題，稱這個最少數(shù)目為 G的蔭度，記為 σ (G)。 納什 威廉斯得到了圖的蔭度計算公式。 定理 8 圖 G的蔭度為： ( ) m a x 1ss mG s? ??? ??? 其中 s是 G的子圖 Hs的頂點數(shù)，而： ? ?m a x ( )sssm E H? 例 6 求 σ (K5)和 σ(K3,3). 2 1 11ss msm s??? ? ? ? ????3 3 21ss msm s??? ? ? ? ????4 6 21ss msm s??? ? ? ? ????5 1 0 31ss msm s??? ? ? ? ????( ) 3G? ?2 1 11ss msm s??? ? ? ? ????3 2 11ss msm s??? ? ? ? ????4 4 21ss msm s??? ? ? ? ????5 6 21ss msm s??? ? ? ? ????3 ,3( ) 3K? ?6 9 21ss msm s??? ? ? ? ???? 定理 9 () 2n nK? ??? ???? ,() 1rs rsK rs? ??? ???? 拜內克給出了完全圖和完全偶圖的森林因子分解。 對于 K2n，將其分解為 n條路 Pi = vivi1vi+1vi2vi+2…v invi+n,腳標按模 2n計算。 對于 K2n+1，先作 n條路 Pi = vivi1vi+1vi2vi+2…v invi+n,腳標按模 2n計算。在每條路外添上點 v2n+1的 n個森林因子； 然后， v2n+1與 v1,v2,…,v 2n分別相連接得一星圖，這是 G的最后一個森林因子。 例 7 對 K7作最小森林因子分解。 v7 v6 v5 v4 v3 v2 v1 1 1 6 2 5 3 4P v v v v v v?2 2 1 3 6 4 5P v v v v v v?3 3 2 4 1 5 6P v v v v v v?v3 v7 v6 v5 v4 v2 v1 v7 v6 v5 v4 v3 v2 v1 v7 v6 v5 v4 v3 v2 v1 v7 v6 v5 v4 v3 v2 v1 例 8 證明：若 n為偶數(shù)，且 δ (G)≥n/2+1 ,則 n階圖 G有 3因子。 證明：因 δ (G)≥n/2+1 ,由狄拉克定理： n階圖 G有 H圈 C .又因 n為偶數(shù)，所以 C為偶圈。于是由 C可得到 G的兩個 1因子。設其中一個為 F1。 考慮 G1=GF1。則 δ(G1)≥n/2。于是 G1中有 H圈 C1. 作 H=C1∪ F1。顯然 H是 G的一個 3因子。 例 9 證明：一棵樹 G有完美匹配當且僅當對所有頂點 v ∈ V(G),有： o(Gv)=1。 證明：“必要性” 一方面：若 G有完美匹配，由托特定理： O(Gv)≦1。 另一方面：若樹 G有完美匹配，則顯然 G為偶階樹，于是O(Gv)≥1。 所以： O(Gv)=1。 “充分性” 由于對任意點 v ∈ V(G), 有 O(Gv)=1。 設 Cv是 Gv的奇分支，又設 G中由 v連到 Gv的奇分支的邊為 vu，顯然，由 u連到 Gu的奇分支的邊也是 uv。 令 M=｛ e(v):它是由 v連到 Gv的邊， v ∈ V(G) ｝ 則： M是 G的完美匹配。 v u 例 10 證明：每個 2k (k0)正則圖是 2可因子分解的。 證明：設 G是 2k連通正則圖， V(G)=｛ v1,v2,…,v n｝ 。則 G存在歐拉環(huán)游 C。 由 C構造偶圖 G1=(X, Y)如下： X=｛ x1,x2,…,x n｝ , Y=｛ y1,y2,…,y n｝ xi與 yj在 G1=(X, Y)中連線當且僅當 vi與 vj在 C中順次相連接。 顯然偶圖 G1=(X, Y)是一個 k正則偶圖。所以 G1可以 1因子分解。 而 G1=(X, Y)的一個 1因子對應于 G中一個 2因子。所以G可以 2因子分解。 作業(yè) P117118 習題 4 ： 3, 4, 5， 6， 7， 8， 9