無(wú)K3子圖的圖中1-因子計(jì)數(shù)

楊 利 民，年 四 洪

(1.大理大學(xué) 數(shù)學(xué)與計(jì)算機(jī)學(xué)院,云南 大理 671003；2.大連理工大學(xué) 數(shù)學(xué)科學(xué)學(xué)院,遼寧 大連 116024)

0 引 言

1-因子或完美匹配在量子化學(xué)、晶體物理學(xué)和計(jì)算機(jī)領(lǐng)域中有重要應(yīng)用．1-因子或完美匹配是覆蓋圖的所有頂點(diǎn)的不交邊的集合．Tutte在1947年給出1-因子或完美匹配存在的一個(gè)充分必要條件[1]．這個(gè)結(jié)果是圖論中的奠基性的定理，在圖論歷史上有重要意義，然而如何判斷1-因子或完美匹配的存在，仍是一個(gè)十分困難的問(wèn)題．相比之下，計(jì)算1-因子的個(gè)數(shù)是更困難的．S(n)-因子計(jì)數(shù)理論包括S(n)-因子的表示公式和分支分析方法．通過(guò)利用已建立的S(n)-因子計(jì)數(shù)理論和組合數(shù)學(xué)方法，可以解決無(wú)K3子圖的圖中1-因子計(jì)數(shù)．

1 定義和引理

定義1令S(n)={Ki：1≤i≤n}，n≥1，并且Ki是有i個(gè)頂點(diǎn)的完全圖，如果M是圖G的一個(gè)子圖，且M的任意分支都同構(gòu)于S(n)={Ki：1≤i≤n}的某一元素，那么M叫作圖G的一個(gè)S(n)-子圖，如果M是圖G的一個(gè)生成子圖，那么M叫作圖G的一個(gè)S(n)-因子．

恰有k個(gè)分支的S(n)-因子的個(gè)數(shù)記為N(G，k)．

S(n)-因子計(jì)數(shù)的表示公式如下．

圖論中分支分析方法公式如下：

2 主要結(jié)果

用f(G)記圖G中1-因子的個(gè)數(shù)．

定理1如果圖G是無(wú)K3子圖或三角形的任意圖，那么f(G)=N(G,n/2)．

證明因?yàn)閳DG是無(wú)K3子圖或三角形的任意圖，所以它就沒(méi)有K4，K5，…，Kn子圖，從而S(n)-因子的元素只能是K1或K2，即每一個(gè)元素是頂點(diǎn)或邊．N(G,n/2)是恰有n/2個(gè)分支的S(n)-因子的個(gè)數(shù)，N(G,n/2)的每一分支都是K2，即邊，而1-因子是覆蓋圖G的不交邊的集合，所以有公式f(G)=N(G,n/2)．

□

其中S(p,n/2)是第二類(lèi)Stirling數(shù)．

因?yàn)閳DG是無(wú)K3子圖或三角形，根據(jù)定理1，得到f(G)=N(G,n/2)，所以無(wú)K3子圖的圖G中1-因子的計(jì)數(shù)公式為

□

例1假設(shè)圖G是一個(gè)完全2-部圖Kn，n，那么

其中s(n，k)是第一類(lèi)Stirling數(shù)，S(p，k)是第二類(lèi)Stirling數(shù)．

通過(guò)定理2，得到完全2-部圖Kn，n的1-因子的計(jì)數(shù)公式

□

推論1對(duì)于兩類(lèi)Stirling數(shù)有組合恒等式：

證明通過(guò)組合計(jì)數(shù)得到在完全2-部圖Kn，n中1-因子的個(gè)數(shù)f(G)=n!．

根據(jù)例1，完全2-部圖Kn，n的1-因子的計(jì)數(shù)公式

所以對(duì)于兩類(lèi)Stirling數(shù)有組合恒等式：

□

證明如果T是一棵樹(shù)，那么T是無(wú)K3子圖或三角形．通過(guò)定理2，得到樹(shù)的1-因子的計(jì)數(shù)公式為

□

推論2對(duì)于兩類(lèi)Stirling數(shù)有組合恒等式：

其中Yp=s(n-1，p-1)，根據(jù)例2，得到

另一方面，在K1，n-1中1-因子的個(gè)數(shù)f(K1，n-1)=0．

綜上所述，對(duì)于兩類(lèi)Stirling數(shù)有組合恒等式：

□

因?yàn)閳DG是一棵樹(shù)，且對(duì)?v∈V，o(G-v)=1，于是在圖G中存在1-因子[1]，得到f(G)≥1．

□

□

以下闡述圖的分支分析方法計(jì)算無(wú)K3子圖的1-因子的計(jì)數(shù)．

定理3如果圖G是有n個(gè)頂點(diǎn)的圖，且為無(wú)K3子圖，P是圖G的一個(gè)固定頂點(diǎn)，通過(guò)頂點(diǎn)P的所有完全圖是Ki1，Ki2，…，Kir，那么圖G中的1-因子的計(jì)數(shù)公式為

其中G-V(Kij)是刪掉頂點(diǎn)V(Kij)和與V(Kij)相關(guān)聯(lián)的邊所得到的圖．

證明因?yàn)閳DG是無(wú)K3子圖，根據(jù)定理1，

f(G)=N(G,n/2)

□

定理4假設(shè)圖G是無(wú)K3子圖，1-因子存在的充分必要條件是N(G,n/2)≥1．

證明略．

復(fù)雜性：計(jì)算N(G,n/2)．

定理5假設(shè)圖G是無(wú)K3子圖，1-因子不存在的充分必要條件是N(G,n/2)=0．

證明略．

例3假設(shè)圖1被構(gòu)造如下，其中Cn是n個(gè)頂點(diǎn)的圈，且n是偶數(shù)，圈Cn的個(gè)數(shù)是q，那么f(G)=2q．

圖1 毽子圖Fig.1 Shuttlecock picture

證明利用分支分析方法，對(duì)固定頂點(diǎn)O進(jìn)行分析，通過(guò)頂點(diǎn)O的所有完全圖是O，OV0，OV1，…，OVq，即K1和(q+1)K2．圖1無(wú)K3子圖．

情況1O作為K1，刪掉頂點(diǎn)O，于是有q個(gè)圈Cn和一個(gè)圈Cn+1，它們兩兩不相交，

N(G-V(K1),k-1)=N(Cn+1∪Cn∪…∪Cn,k-1)

情況2過(guò)O點(diǎn)的完全圖為OV0，刪掉OV0，于是有q個(gè)圈Cn和一個(gè)路Pn-1，它們兩兩不相交，

N(G-V(K1),k-1)=N(Pn-1∪Cn∪…∪Cn,k-1)

情況3過(guò)O點(diǎn)的完全圖為OV1，OV2，…，OVq，刪掉OV1，OV2，…，OVq，因?yàn)镺V1，OV2，…，OVq是對(duì)稱(chēng)的，于是

N(G-V(OV1),k-1)=

N(G-V(OV2),k-1)=…=

N(G-V(OVq),k-1)=

N(Cn+1∪Pn-2∪Cn∪…∪Cn,k-1),

N(G-V(OV1),k-1)+N(G-V(OV2),k-1)+

…+N(G-V(OVq),k-1)=

qN(Cn+1∪Pn-2∪Cn∪…∪Cn,k-1)

利用引理2和5，有

N(G-V(K1),k-1)+

N(G-V(OV0),k-1)+

N(G-V(OV1),k-1)+

N(G-V(OV2),k-1)+…+

N(G-V(OVq),k-1)=

N(Cn+1∪Cn∪…∪Cn,k-1)+

N(Pn-1∪Cn∪…∪Cn,k-1)+

qN(Cn+1∪Pn-2∪Cn∪…∪Cn,k-1)=

N(Cn,l3)…N(Cn,lq+1))

圖1中頂點(diǎn)的個(gè)數(shù)是(q+1)n+2．根據(jù)定理3、引理3和引理4[5-6]，

f(G)=0+2q+q×0=2q．

圖1中存在1-因子，且為2q個(gè)．

□

例4假設(shè)圖2被構(gòu)造如下，其中Pn是長(zhǎng)度為n且有n+1個(gè)頂點(diǎn)，Pn的個(gè)數(shù)是q，那么f(G)=0．

圖2 棒圖Fig.2 Bar graph

證明類(lèi)比于例3，利用圖的分支分析方法，對(duì)固定點(diǎn)O進(jìn)行分析．通過(guò)頂點(diǎn)O的所有完全圖是K1和q個(gè)K2．圖2無(wú)K3子圖．

情況1O作為K1，為一個(gè)完全分支，刪掉K1，有q個(gè)路Pn-1，并且兩兩不相交，于是

N(G-V(K1),k-1)=N(Pn-1∪Pn-1∪…∪

Pn-1,k-1)

情況2O含于K2，作為一個(gè)完全分支，刪掉K2，有一個(gè)路Pn-2和q-1個(gè)路Pn-1，因?yàn)閝個(gè)完全圖K2是對(duì)稱(chēng)的，于是

qN(G-V(K2),k-1)=qN(Pn-2∪Pn-1∪…∪

Pn-1,k-1)

綜上所述，根據(jù)引理2和5，得到

N(G-V(K1),k-1)+

qN(G-V(K2),k-1)=

N(Pn-1∪Pn-1∪…∪Pn-1,k-1)+

qN(Pn-2∪Pn-1∪…∪Pn-1,k-1)=

N(Pn-1,lq)+

圖2中頂點(diǎn)的個(gè)數(shù)是qn+1，由于圖2無(wú)K3子圖，根據(jù)定理3和引理3，有

當(dāng)q或n是偶數(shù)時(shí)，qn+1是奇數(shù)，在圖2中，f(G)=0．

當(dāng)q和n都是奇數(shù)時(shí)，qn+1是偶數(shù)，在圖2中，f(G)=0+q×0=0[7]．

在圖2中，對(duì)任意q和n，不存在1-因子．

□

注構(gòu)造這兩類(lèi)圖，1-因子可能無(wú)限或?yàn)榱悖?/p>

定理6對(duì)任意自然數(shù)N，存在連通圖使得它的1-因子個(gè)數(shù)大于自然數(shù)N．

證明構(gòu)造一個(gè)圖，如例3的圖1，根據(jù)例3的結(jié)果，該圖的1-因子個(gè)數(shù)f(G)=2q．

□

3 結(jié) 語(yǔ)

1-因子或完美匹配的計(jì)數(shù)是十分困難和有價(jià)值的問(wèn)題．本文利用S(n)-因子計(jì)數(shù)理論和組合數(shù)學(xué)方法研究了無(wú)K3子圖的圖中的1-因子計(jì)數(shù)，取得了一定的進(jìn)展，對(duì)于組合學(xué)和圖論具有一定參考價(jià)值．