圖的覆蓋數(shù)與分子的凱庫勒結(jié)構(gòu)

胡啟明，許 歡，袁曉彤

(合肥幼兒師范高等專科學(xué)校公共教學(xué)部，安徽 合肥 230013)

0 引言

圖1 G1

圖2 G2

求圖的最小頂點(diǎn)覆蓋被稱為頂點(diǎn)覆蓋問題(vertex cover problem，VCP)，VCP是理論計(jì)算機(jī)科學(xué)和離散數(shù)學(xué)中一個(gè)經(jīng)典NP完全問題，可追溯到20世紀(jì)30年代Konig的經(jīng)典結(jié)果[1].1972年KARP[2]證明了VCP對(duì)于一般圖是NP完全的.求圖的最小邊覆蓋被稱為邊覆蓋問題，該問題是由RABIN[3]首先提出的.邊覆蓋在交通相位問題中起著重要的作用，可應(yīng)用于網(wǎng)絡(luò)分析.到目前為止，只有Mangoldt圖得到了最小邊覆蓋[4].

不失一般性，將化學(xué)分子結(jié)構(gòu)看成一個(gè)圖，其頂點(diǎn)對(duì)應(yīng)于化合物的原子，邊對(duì)應(yīng)于隱藏于化合物中的化學(xué)鍵，稱之為化學(xué)圖.多數(shù)情況下，化學(xué)圖的頂點(diǎn)度都小于或等于4.化學(xué)圖論是數(shù)學(xué)化學(xué)的一個(gè)分支，化學(xué)圖論模型已被廣泛應(yīng)用于預(yù)測(cè)化合物的性質(zhì)[5].在過去幾十年里，學(xué)者們對(duì)化合物凱庫勒結(jié)構(gòu)的研究積累了許多成果[6-7].

有凱庫勒結(jié)構(gòu)的化學(xué)分子，相當(dāng)于含有完美匹配的化學(xué)圖[8].若一個(gè)圖含有完美匹配，則稱它為凱庫勒?qǐng)D.從圖論觀點(diǎn)看，凱庫勒?qǐng)D是一個(gè)有趣問題，如果不分析覆蓋數(shù)，這個(gè)問題將是未知的.部分學(xué)者對(duì)凱庫勒結(jié)構(gòu)進(jìn)行了大量的研究[7-8]，但尚沒有將覆蓋數(shù)與凱庫勒結(jié)構(gòu)聯(lián)系在一起的研究.在化學(xué)圖中，使覆蓋問題有意義的，是它與凱庫勒結(jié)構(gòu)的緊密聯(lián)系.因此，本文將討論圖的覆蓋問題，并用覆蓋數(shù)刻畫感興趣的化學(xué)圖，通過計(jì)算一些特殊圖的點(diǎn)覆蓋數(shù)和邊覆蓋數(shù)，來刻畫覆蓋數(shù)和凱庫勒結(jié)構(gòu)的相關(guān)性.

1 凱庫勒?qǐng)D的充要條件

定理1.1 設(shè)G=(V,E)是二部圖，則圖G是一個(gè)凱庫勒?qǐng)D?β(G)=β′(G).

證明 “?”假設(shè)圖G是一個(gè)凱庫勒?qǐng)D.

“?”假設(shè)β(G)=β′(G).

2 因子臨界圖

近似完美匹配，是指圖中存在只剩下一個(gè)頂點(diǎn)未被包含的最大匹配.若對(duì)于圖中每個(gè)頂點(diǎn)都有一個(gè)近似完美匹配，則稱該圖為因子臨界圖.也就是說，如果去掉因子臨界圖中的任何一個(gè)頂點(diǎn)，它就變成了凱庫勒?qǐng)D.

3 頂部梯狀圖

如圖3所示，把頂部梯狀圖記為TLn，n≥0，它們有頂端a和基對(duì)b1,b2，與頂端a相鄰的兩條邊稱為圖的頂部，連接基對(duì)的邊稱為圖的底部，由底部向下添加梯級(jí)(2個(gè)頂點(diǎn)、3條邊)構(gòu)成梯形圖.

例如，TL0(即完全圖K3)可指定其任一個(gè)頂點(diǎn)為頂端，其余兩個(gè)頂點(diǎn)為基對(duì)；又如，TL1(類似于房屋圖)是一個(gè)含有5個(gè)頂點(diǎn)和6條邊的簡單圖.一般地，任一頂部梯狀圖TLn，n≥0，都有2n+3個(gè)頂點(diǎn)和3(n+1)條邊.這類圖包含近似完美匹配，即頂部梯狀圖都是因子臨界圖.

(a)TL0 (b)TL1 (c)TLn圖3 頂部梯狀圖

定理3.1 若G是一個(gè)頂部梯狀圖TLn，則β(G)=n+2，n≥0.

證明 用數(shù)學(xué)歸納法，

當(dāng)n=0時(shí)，G為TL0是K3，此時(shí)，β(G)=β(TL0)=2=0+2；

當(dāng)n=1時(shí)，G為TL1是房屋圖，此時(shí)，β(G)=β(TL1)=3=1+2；

假設(shè)當(dāng)n=k時(shí)，結(jié)論成立，即有β(TLk)=k+2,下面證明n=k+1的情況.

由頂部梯狀圖的構(gòu)造易知，TLk+1是在TLk基礎(chǔ)上增加了2個(gè)新頂點(diǎn)和3條新邊.顯然，只要在TLk的覆蓋里添加1個(gè)新頂點(diǎn)即可得TLk+1的一個(gè)覆蓋.則有β(TLk+1)=β(TLk)+1.從而β(TLk+1)=k+3=(k+1)+2.

因此，對(duì)于所有的n≥0，都有β(G)=B(TLn)=n+2.

定理3.2 若G是一個(gè)頂部梯狀圖TLn，則對(duì)于所有的n≥0，都有β′(G)=β(G).

證明 設(shè)G(V,E)是一個(gè)頂部梯狀圖TLn.

4 廣義梯形圖

設(shè)TLn1和TLn2是兩個(gè)頂部梯狀圖(兩邊的梯級(jí)數(shù)即梯形圖的尺寸分別為n1和n2)，連接TLn1和TLn2的兩個(gè)頂端點(diǎn)構(gòu)成邊(稱之為橋)，產(chǎn)生的新圖記為L(n1,n2). 此類圖含有完美匹配，即為凱庫勒?qǐng)D.

以L(n1,n2)的橋的兩個(gè)頂端點(diǎn)為基對(duì)再構(gòu)造n3個(gè)梯級(jí)，記為L(n1,n2,n3).易知，這一類圖含有完善匹配.分別連接L(n1,n2)中的TLn1和TLn2兩組基對(duì)點(diǎn)構(gòu)成邊(稱之為懸掛邊)，這樣產(chǎn)生的新圖記為L(n1,n2,M).

不失一般性，在頂部梯狀圖的頂端和基部分別構(gòu)造橋和懸掛邊，產(chǎn)生的圖(圖4)記為L(n1,n2,n3，M)，稱為廣義梯形圖.

圖4 L(n1,n2,n3,M)

定理4.1 設(shè)G=L(n1,n2,n3,M)，則對(duì)于任意的n1≥0，n2≥0和n3≥0，都有β(G)=n1+n2+n3+4.

證明 分情況討論，

(1)若n1=n2=n3=0(圖5)，圖G中含有2個(gè)三角形、2個(gè)懸掛邊和1個(gè)橋，則需要從每個(gè)三角形中各選擇2個(gè)頂點(diǎn)來覆蓋圖中的9條邊.此時(shí)，β(G)=2+2=4.

圖5 L(0,0,0,M)

(2)若n1=n2=0，n3≠0(圖6)，則需要n3個(gè)頂點(diǎn)覆蓋尺寸為n3的梯形圖，需要4個(gè)頂點(diǎn)覆蓋2個(gè)三角形、2個(gè)懸掛邊和1個(gè)橋.此時(shí)，β(G)=n3+4.

圖6 L(0,0,n3,M)

(3)若n1=n2≠0，n3≠0，則分別需要n1，n2和n3個(gè)頂點(diǎn)覆蓋圖G中3個(gè)梯級(jí).同時(shí)，圖G中含有2個(gè)三角形、2個(gè)懸掛邊和1個(gè)橋，需要4個(gè)頂點(diǎn)來覆蓋.此時(shí)，β(G)=n1+n2+n3+4.

(4)若n1≠n2≠0，n3≠0，當(dāng)n1n2時(shí)，所得圖是同構(gòu)的.可得，β(G)=n1+n2+n3+n3+4.

定理4.2 設(shè)G=L(n1,n2,n3,M)，則對(duì)于任意的n1≥0，n2≥0和n3≥0，都有β′(G)=n1+n2+n3+3.

因?yàn)镚=L(n1,n2,n3,M)含有完美匹配，所以，