圖的最大匹配個數的下界

翟紹輝,郭利濤,鄭藝容,莊 蔚

(廈門理工學院應用數學學院,福建廈門361024)

1 預備知識

本文中所討論的圖都是簡單圖,未定義的符號請參閱文獻[1-2].

設G是一個具有n個頂點的圖,V(G)和E(G)分別表示G中的頂點集和邊集.如果G中某個頂點的度數為零,則稱該頂點為孤立點.設M是E(G)的一個子集,若M中任意兩條邊都沒有公共頂點,則稱M是G的一個匹配.如果|M|=k≥1,則稱M是G的一個k-匹配,這里|M|表示M中邊的個數.特別地,如果G中沒有匹配M′使得|M′|>|M|,則稱M是G中的最大匹配.設v是G中任意一點,若v與M中的某條邊相關聯,則稱M飽和v.如果M是G中的最大匹配且|M|=k,那么G中恰有(n-2k)個頂點未被M飽和,因此也稱該k-匹配M是虧(n-2k)-匹配.特別地,若n-2k=0或n-2k=1,則分別稱M是G的完美匹配或幾乎完美匹配.令m(G)表示G中最大匹配個數,特別地,如果G有完美匹配,則用pm(G)表示G中完美匹配個數.

若G是一個具有完美匹配的圖,則有pm(G)≥ 1.當pm(G)=1時,即G具有唯一完美匹配時,下面定理給出了這類圖的刻畫.

定理1[2,Corollary 5.3.12]一個圖G有唯一完美匹配的充分必要條件是G可以通過以下遞歸方式構造出來:設G1和G2是兩個點不交的圖,且都具有唯一的完美匹配,設x1和x2是兩個新點,連接xi和Gi中的至少一個點,并且連接x1和x2,這里i=1,2.

特別的,對于無割邊三正則圖,Petersen[3]證明了這類圖有完美匹配.Lovsz等[2，Conjecture 8.1.8]給出了下面的猜想

猜想1[2]存在一個正整數0<ε<1,使得對任意無割邊三正則圖G,有

pm(G)≥2ε|V(G)|.

目前,這個猜想仍然沒有被解決,現已有的相關結論可以參考文獻[3-7]等.另外,關于特殊圖類(例如:樹)的最大匹配的計數問題,也有一些相關的研究,詳見文獻[8-9]等.

本文中考慮的圖是具有最大匹配(不是完美匹配)的一般圖,證明了任意具有n個頂點且最大匹配為k-匹配的連通圖都至少有n-2k+1個互不相同的最大匹配,這里n≥2k+1.另外,還刻畫了恰好具有n-2k+1個最大匹配的圖.

為了證明本文中的主要結論,需要引入下面一些定義符號和已知的結論.假設S是V(G)的一個子集,NG(S)表示V(G)中所有與S中頂點相鄰的頂點集合.Hall[10]給出了下面結論.

定理2[10]二部圖G=(A,B)有飽和A中所有頂點的最大匹配的充分必要條件是對任意S?A,有|NG(S)|≥|S|.

設G=(A,B)是一個二部圖,如果對任意非空集合S?A都有|NG(S)|>|S|成立,則稱G有正盈余(對于A).根據定理2,若G=(A,B)是二部圖且對A有正盈余,則G有飽和A中所有頂點的最大匹配.

設G是一個具有n個頂點的圖,若任意刪去G中p個頂點后余圖都有完美匹配,則稱G是p-因子臨界圖.特別地,若p=1,則稱G是因子臨界圖.設S是V(G)的一個子集,G[S]表示由S導出的子圖.令D(G)表示V(G)中所有至少被G中某個最大匹配未飽和的頂點所組成的集合,A(G)表示V(G)-D(G)中至少與D(G)中一個頂點相鄰的頂點集合,C(G)=V(G)-D(G)-A(G).刪去C(G)中所有頂點和由A(G)在G中導出子圖的邊,并且分別收縮D(G)的導出子圖的每個分支為一個頂點,則所得到的新圖記為B(G).

定理3[2,Theorem 3.2.1](Gallai-Edmonds結構定理)設G是一個圖,D(G),A(G),C(G)和B(G)如上述所定義,則有以下結論成立:

(i)D(G)的導出子圖的每一個分支都是因子臨界的;

(ii)C(G)的導出子圖都有完美匹配;

(iii)B(G)是二部圖并且有正盈余(對于A(G));

(iv)G的最大匹配包含D(G)中每個分支的幾乎完美匹配,C(G)中每個分支的完美匹配和飽和A(G)中所有頂點與D(G)中不同分支的匹配;

2 主要結論

定理4設G是一個具有n個頂點,最大匹配為k-匹配且沒有孤立點的連通圖,則有m(G)≥n-2k+1,這里n≥2k+1.

證明設M是G的一個最大匹配且有|M|=k,v1,…,vn-2k是沒有被M飽和的頂點集合.由于M是G的最大匹配,則由v1,…,vn-2k在G中的導出子圖G[v1,…,vn-2k]是空圖.又因為G中沒有孤立點,所以對每個vi都存在有一邊ei連接vi和V(M)中的某個點,不妨設該點為ui,這里i∈{1,2，…,n-2k}.設f是M中的一邊且飽和ui,則可以得到一個不同于M的最大匹配Mvi=M-{f}∪{ei}.類似地,可以得到至少n-2k個互不相同的最大匹配Mv1,…,Mvn-2k,且都不同于M.因此有m(G)≥n-2k+1成立,證畢.

根據二部圖正盈余的定義,可以得到如下結論.

引理1設G=(A,B)是一個二部圖并且對A有正盈余,則G的任意一邊都包含在G中的某個最大匹配中.

證明設e=uv是G中任意一邊,不妨進一步假設u∈A,v∈B.令A′=A-{u},B′=B-{v}和G′=(A′,B′).對任意S?A′有|NG′(S)|+1≥|NG(S)|成立.由于G對A有正盈余,則有|NG(S)|>|S|.綜合上述兩個式子可以得到|NG′(S)|≥|S|,根據定理2,則G′有最大匹配且飽和A′中的所有頂點.不妨設該最大匹配為M′,令M=M′∪{e},則M是G中的最大匹配且包含e.因此G的任意一邊都包含在G中的某個最大匹配中,證畢.

引理2設G是一個具有n個頂點且最大匹配為k-匹配的連通圖,這里n≥2k+1,C(G),A(G),D(G)和B(G)如引言中所定義.設D1,…,Ds是D(G)中的所有分支.若C(G)≠?,則有m(G)≥pm(C(G))m(B(G))且等號成立的充分必要條件是D1,…,Ds都是單點集.若C(G)=?,則有m(G)≥m(B(G))且等號成立的充分必要條件是D1,…,Ds都是單點集.

證明這里僅證明C(G)≠?的情形,對于C(G)=?的情形可以類似的給出證明,這里不再贅述.根據Gallai-Edmonds結構定理的(iv),容易驗證m(G)≥pm(C(G))m(B(G)).下面證明m(G)=pm(C(G))m(B(G))成立的充分必要條件是D1,…,Ds都是單點集.

充分性:當D1,…,Ds都是單點集,容易得到m(G)=pm(C(G))m(B(G))成立.

必要性:反證,不妨假定|D1|≥3.假設u1v1,…,ulvl是G中連接D1和A(G)的邊,這里l≥1,u1,…,ul∈A(G),v1,…,vl∈D1.設v∈B(G)是由D1收縮后得到的頂點,那么u1v,…,ulv是B(G)中連接v和A(G)的邊.根據Gallai-Edmonds結構定理的(v)可以得到以下不等式

m(G)≥pm(C(G))[m(B(G)-v))m(D1)+

(1)

由于D1是因子臨界的,則有pm(D1-vi)≥1成立;由于C(G)≠?,則pm(C(G))≥1成立;根據定理4,可以得到m(D1)≥2成立.因此式(1)可以化簡為

m(G)≥pm(C(G))[m(B(G)-v))+

pm(C(G))m(B(G)-v)).

(2)

已知G是連通圖,則根據Gallai-Edmonds結構定理和B(G)的構造方法可知B(G)是沒有孤立點的二部圖,并且B(G)的最大匹配也是虧(n-2k)-匹配.因為B(G)對A(G)有正盈余,則在B(G)中,A(G)的任意一點的度數都不小于2.因此可以進一步得到B(G)-v也沒有孤立點.另外,根據B(G)對A(G)有正盈余和引理1可得B(G)-v有飽和A(G)中所有頂點的最大匹配,并且此時的最大匹配是虧(n-2k-1)-匹配.根據定理4有下面不等式成立

m(B(G)-v))≥n-2k≥1.

根據上述得到的pm(C(G))≥1和m(B(G)-v))≥n-2k≥1,則式(2)可以變為

m(G)≥pm(C(G))[m(B(G)-v))+

1=pm(C(G))m(B(G))+1>

pm(C(G))m(B(G)).

這與m(G)=pm(C(G))m(B(G))矛盾.因此,當m(G)=pm(C(G))m(B(G))時,D1,…，Ds都是單點集,證畢.

對于一個具有n個頂點且最大匹配為k-匹配的連通圖G,下面定理刻畫了恰好具有n-2k+1個最大匹配的圖.

定理5設G是一個具有n個頂點,最大匹配為k-匹配的連通圖,且恰好有n-2k+1個互不相同的最大匹配,這里n≥2k+1且k≥1,那么根據Gallai-Edmonds結構定理,G的結構如下:

(i)C(G)具有唯一的完美匹配或C(G)=?;

(ii)A(G)恰好只有一個點;

(iii)D(G)的每一個分支都是一個單點集.

證明設G恰好只有n-2k+1個互不相同的最大匹配(k-匹配),即m(G)=n-2k+1.根據B(G)的構造方法可知,當G有虧(n-2k)-匹配時,那么B(G)也有虧(n-2k)-匹配.根據定理4有

慕課不斷發展的同時對教師的教學能力、專業知識儲備量也提出了更高的要求[10]。在傳統課堂上，有些教師可能總是重復以往的知識點，而忽略了最新的知識內容。在慕課這個平臺上，教師如果想進行問題模式的教學，首要的就是豐富自己的知識。只有教師不斷的提升理論水平、實踐能力，并將兩者融匯貫通，才能有效指導學生完成對知識的分析、整合、歸納、演繹，最終內化于心的過程[11]。并且與此同時，教師不僅可以將自己的專業知識分享給別人，還可以學習到最全面最新穎的知識點，而且還可以自己設計問題和學習者進行線上討論，通過有趣的學習方法讓學生更好的掌握知識，做到了提高自身專業知識的同時，改革了教學方法。

m(B(G))≥n-2k+1.

(3)

根據Gallai-Edmonds結構定理的(i),如果C(G)≠?,那么C(G)的導出子圖有完美匹配,則有

pm(C(G))≥1.

(4)

根據引理2有

m(G)≥pm(C(G))m(B(G)).

(5)

根據m(G)=n-2k+1和式(3)～(5)可以得到m(G)=m(B(G))=n-2k+1和pm(C(G))=1,即C(G)只有唯一的完美匹配.

如果C(G)=?,那么根據引理2有

(6)

根據m(G)=n-2k+1和式(3),(6)可以得到

m(G)=m(B(G))=n-2k+1.

綜上,無論C(G)是否為空集,均有m(B(G))=n-2k+1.根據引理2,可以得到D(G)中每一個分支都是單點集,這就證明了定理中的(i)和(iii).

下面證明(ii).由于k≥1,則A(G)≠?.現在采用反證法證明A(G)恰好只有一個點.假設A(G)={u1,…,us}且s≥2.根據Gallai-Edmonds結構定理,B(G)是二部圖,A(G)和V(B(G))-A(G)恰好是B(G)的一個二部劃分.由于G是連通的且最大匹配是虧(n-2k)-匹配,則B(G)沒有孤立點且最大匹配也是虧(n-2k)-匹配.由于|A(G)|=s≥2,則可以得到B(G)的最大匹配中邊的個數為s.

設M是B(G)的最大匹配(或虧(n-2k)-匹配),則|M|=s≥2.不妨設u1v1∈M,這里v1∈V(B(G))-A(G),u1∈A(G),顯然M飽和A(G)中所有點.

情形1B(G)-u1-v1沒有孤立點.

此時M-{u1v1}是圖B(G)-u1-v1的最大匹配,且也是B(G)-u1-v1的虧(n-2k)-匹配.根據定理4,m(B(G)-u1-v1)≥n-2k+1.設M1,…Mn-2k+1是B(G)-u1-v1中互不相同的最大匹配,則M1∪{u1v1},…,Mn-2k+1∪{u1v1}也是B(G)中互不相同的最大匹配.由于B(G)是二部圖且對A(G)有正盈余,則u1在B(G)中至少是2度點.設v2是u1在B(G)中除v1以外的一個鄰點,即u1v2∈E(B(G)).根據引理1,B(G)中存在一個最大匹配M′使得u1v2∈M′,且M′不同于M1∪{u1v1},…,Mn-2k+1∪{u1v1}.這樣就得到B(G)中n-2k+2個互不相同的最大匹配,這與m(B(G))=n-2k+1矛盾.

情形2B(G)-u1-v1有孤立點.

不妨設w1,…,wt是B(G)-u1-v1中的孤立點,顯然,w1,…,wt∈V(B(G))-A(G)-{v1}.由于M-{u1v1}是B(G)-u1-v1的最大匹配,同樣也是B(G)-u1-v1的虧(n-2k)-匹配,因此可以得到1≤t≤n-2k.設S表示由點集{w1,…,wt,u1,v1}的導出子圖,則S是星圖,即在S中頂點u1的度數為t+1,其余頂點度數均為1.容易得到m(S)=t+1且{u1v1},{u1w1},…,{u1wt}分別是S的最大匹配.

(i) 1≤t

此時M-{u1v1}是B(G)-u1-v1的最大匹配,也是B(G)-V(S)中的最大匹配,同樣也是B(G)-V(S)的虧(n-2k-t)-匹配,并且B(G)-V(S)沒有孤立點.根據定理4,可以得到m(B(G)-V(S))≥n-2k-t+1.另外,容易看出S中任意一個最大匹配和B(G)-V(S)中任意一個最大匹配的并集恰好是B(G)的一個最大匹配,因此有以下不等式成立

m(B(G))≥m(S)m(B(G)-V(S))≥

(t+1)(n-2k-t+1)>n-2k+1,

這與m(B(G))=n-2k+1矛盾.

(ii)t=n-2k.

此時M-{u1v1}是圖B(G)-V(S)中的完美匹配.由于B(G)是二部圖且對A(G)有正盈余,因此S和(B(G)-V(S))∩(A(G)-u1)至少有一邊連接.不妨設e是其中一條邊,根據引理1,B(G)中存在一個最大匹配包含e,不妨設為Me.則Me,(M-{u1v1})∪{u1v1},(M-{u1v1})∪{u1w1},…,(M-{u1v1})∪{u1wn-2k}均是B(G)中互不相同的最大匹配,且共有n-2k+2個最大匹配,這與m(B(G))=n-2k+1矛盾.

綜上各種情形可以得到,A(G)只能有一個單點,這樣就證明了(ii),證畢.