一類3-正則圖完美對集的計數

唐 保 祥， 任 韓

( 1.天水師范學院 數學與統計學院, 甘肅 天水 741001；2.華東師范大學 數學系, 上海 200062 )

0 引 言

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

1 基本概念

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

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

2 主要結果

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

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

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

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

因為u1w3∈P2，所以u2w1，w2u12∈P2，由β(n)的定義可知，|P2|=β(n-1)．

因此，

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

(1)

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

因為u1w2∈M1，所以u2w1，w3u13∈M1，由α(n)的定義可知，|M1|=α(n-1)．

因此，

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

(2)

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

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

(3)

因為su11∈N1，所以su12，su13，u11v12，u11v13?N1，因為G1?G3，由α(n)的定義可知，|N1|=α(n-1)．

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

因為su13∈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的完美對集數為3n+1的一個組合證明．

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

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

3 結 語

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