一類3-正則圖完美對(duì)集的計(jì)數(shù)

唐 保 祥， 任 韓

( 1.天水師范學(xué)院 數(shù)學(xué)與統(tǒng)計(jì)學(xué)院, 甘肅 天水 741001；2.華東師范大學(xué) 數(shù)學(xué)系, 上海 200062 )

0 引 言

圖的完美對(duì)集計(jì)數(shù)理論的研究成果已經(jīng)在計(jì)算機(jī)科學(xué)、物理學(xué)和化學(xué)等多個(gè)領(lǐng)域有廣泛的應(yīng)用．例如，DNA計(jì)算自組裝模型的算法理論，計(jì)算機(jī)積和式二分圖的完美對(duì)集表示，化學(xué)中共軛分子圖Kekulé結(jié)構(gòu)的完美對(duì)集表示，此外完美對(duì)集數(shù)還是估計(jì)共振能量和π-電子能量的重要指標(biāo)．因此，研究圖的完美對(duì)集計(jì)數(shù)理論有重要的理論價(jià)值和現(xiàn)實(shí)意義[1-3]．但是，此問題已經(jīng)被證實(shí)是NP-難問題．分類嵌套遞推的方法是求解許多類圖完美對(duì)集數(shù)非常有效的方法[4-8]．本文構(gòu)造一類新的3-正則圖2-3-nC6，用分類嵌套遞推的方法求出圖2-3-nC6中不同完美對(duì)集的計(jì)數(shù)公式．

1 基本概念

定義1若圖G有一個(gè)1-正則生成子圖P，則稱這個(gè)生成子圖P為圖G的完美對(duì)集．

定義2設(shè)圖G是一個(gè)有完美對(duì)集的圖，若圖G的兩個(gè)完美對(duì)集P1和P2中有一條邊不同，則稱P1和P2是G的兩個(gè)不同完美對(duì)集．

2 主要結(jié)果

定理1設(shè)圖2-3-nC6的完美對(duì)集數(shù)為ρ(n)，則ρ(n)=3n+1．

證明顯然{su12，u11v13，v11u13，v12u22，u21v23，v21u23，…，vn-1，2un2，un1vn3，vn1un3，vn2t}是圖2-3-nC6的一個(gè)完美對(duì)集．因此，可設(shè)圖2-3-nC6的完美對(duì)集數(shù)為ρ(n)．欲求ρ(n)的解析式，分別定義3個(gè)圖G1、G2和G3，并求出它們的完美對(duì)集數(shù)的遞推式．把路w1u2w3的端點(diǎn)w1、w3分別與圖2-3-nC6頂點(diǎn)u11、u13各連接一條邊，再把路w2u1w3的端點(diǎn)w2、w3分別與圖2-3-nC6頂點(diǎn)u12、u13各連接一條邊，最后刪除圖2-3-nC6的頂點(diǎn)s，這樣產(chǎn)生的圖記為G1，如圖2所示．類似地定義圖G2、G3，見圖3、4．

顯然{u1w2，u2w1，w3u13，u11v12，u12v11，v13u23，…，un1vn2，un2vn1，vn2t}是圖G1的完美對(duì)集．容易判斷圖G2、G3有完美對(duì)集．顯然G1?G3．α(n)、β(n)分別表示圖G1、G2完美對(duì)集的數(shù)目．則圖G3的完美對(duì)集數(shù)為α(n)．

下面證明α(n)=β(n)．設(shè)圖G1完美對(duì)集的集合為P，圖G1含邊u1w2、u1w3的完美對(duì)集集合分別記為P1、P2，則P1∩P2=?，P=P1∪P2，故α(n)=|P|=|P1|+|P2|．

因?yàn)閡1w3∈P2，所以u(píng)2w1，w2u12∈P2，由β(n)的定義可知，|P2|=β(n-1)．

因此，

α(n)=2α(n-1)+β(n-1)

(1)

設(shè)圖G2完美對(duì)集的集合為M，圖G2含邊u1w2、u1w3的完美對(duì)集集合分別記為M1、M2，則M1∩M2=?，M=M1∪M2，故β(n)=|M|=|M1|+|M2|．

因?yàn)閡1w2∈M1，所以u(píng)2w1，w3u13∈M1，由α(n)的定義可知，|M1|=α(n-1)．

因此，

β(n)=2α(n-1)+β(n-1)

(2)

由式(1)和(2)可知，

α(n)=β(n)=3α(n-1)

(3)

因?yàn)閟u11∈N1，所以su12，su13，u11v12，u11v13?N1，因?yàn)镚1?G3，由α(n)的定義可知，|N1|=α(n-1)．

因?yàn)閟u12∈N2，所以su11，su13，u12v11，u12v13?N2，由β(n)的定義可知，|N2|=β(n-1)=α(n-1)．

因?yàn)閟u13∈N3，所以su11，su12，u13v11，u13v12?N3，由α(n)的定義可知，|N3|=α(n-1)．

綜上所述，

ρ(n)=3α(n-1)

(4)

由式(3)和(4)，得ρ(n)=3n-1α(1)．

由圖5知，α(1)=9，故ρ(n)=3n+1．證畢．

下面再給出圖2-3-nC6的完美對(duì)集數(shù)為3n+1的一個(gè)組合證明．

事實(shí)上，飽和圖2-3-nC6頂點(diǎn)s的完美對(duì)集的邊有3種選擇，分別是邊su11、su12、su13，當(dāng)邊su1i(i=1，2，3)被選定，每個(gè)完美對(duì)集都要從4條邊u1jv1k中選取2條邊(j，k∈{1，2，3}，j≠i，k≠i)，也就是在圈u11v12u13v11u12v13u11上除邊u1iv1j、u1iv1k(i，j，k互不相等)的4條邊中選取不相鄰的2條邊，有3種選擇；當(dāng)u1jv1k中的2條邊選定之后，邊v11u21、v12u22、v13u23中有唯一確定的邊在完美對(duì)集中；如此下去，每個(gè)圈ut1vt2ut3vt1ut2vt3ut1(t=1，2，…，n)中選取2條不相鄰的邊在完美對(duì)集中，都有3種選擇，按乘法原理，共有3n+1種選擇邊的方法，因此圖2-3-nC6的完美對(duì)集數(shù)為3n+1．

例1ρ(1)=9，圖2-3-1×C6的9個(gè)不同完美對(duì)集見圖6．

3 結(jié) 語

圖的完美對(duì)集計(jì)數(shù)問題研究具有重要的理論價(jià)值和現(xiàn)實(shí)意義．但是，一般圖的完美對(duì)集計(jì)數(shù)問題卻是NP-難問題．本文方法研究了計(jì)算一般的有完美對(duì)集圖的所有完美對(duì)集數(shù)的可能性．很多存在完美對(duì)集圖都能利用本文方法求出它的完美對(duì)集數(shù)的遞推式，由于高階遞推式的特征方程是一個(gè)高次代數(shù)方程，而一般的5次及以上代數(shù)方程沒有根式解，一般的圖很難求出它的完美對(duì)集數(shù)遞推式的通解．但是，從應(yīng)用角度來看，遞推式更容易算出一個(gè)圖的完美對(duì)集數(shù)．因此，本文方法為圖的完美對(duì)集應(yīng)用提供了有力支持．