王琪瑞++帥天平

摘要：覆蓋問題是圖論的主要研究?jī)?nèi)容，也是理論計(jì)算機(jī)科學(xué)中的重要內(nèi)容之一，具有重要的理論意義與應(yīng)用價(jià)值，在計(jì)算機(jī)圖形學(xué)和運(yùn)籌學(xué)中都有廣闊的應(yīng)用前景。在通信行業(yè)，基于覆蓋問題的研究基礎(chǔ)，可以簡(jiǎn)化通信網(wǎng)絡(luò)的層次分布與優(yōu)化。特殊的覆蓋可以導(dǎo)出圖的一些良好的性質(zhì)，鑒于這類問題在實(shí)際應(yīng)用中的價(jià)值，此類研究近期應(yīng)用于圖的結(jié)構(gòu)性之上。圖論中的覆蓋問題有很多種，其中包括等可覆蓋問題：如果一個(gè)圖G的每個(gè)極小H-覆蓋都是它的最小H-覆蓋，則稱G為H-等可覆蓋的。本文僅考慮H為P4時(shí)的情形。經(jīng)過討論，本文通過對(duì)含4一圈且不合3一圈的圖的特征進(jìn)行刻畫，給出了判定任意一個(gè)含4-圈且不含3-圈的圖是否是P4-等可覆蓋的充分必要條件。

關(guān)鍵詞：計(jì)算機(jī)軟件與理論；等可覆蓋；圖論；覆蓋

中圖分類號(hào)：0157.5 文獻(xiàn)標(biāo)識(shí)碼：A DOI：10.3969/j.issn.1003-6970.2015.10.002

引言

圖論是組合數(shù)學(xué)的一個(gè)重要分支，在計(jì)理論算機(jī)科學(xué)領(lǐng)域有著極其重要的地位和作用。近些年來，理論計(jì)算機(jī)科學(xué)的迅猛發(fā)展和理論需求大大推動(dòng)了圖論的發(fā)展，同時(shí)也為圖論的研究帶來了越來越多的新課題。圖論中的問題相當(dāng)豐富，其中，覆蓋問題作為非常重要而又基本的問題，多年來一直受到國(guó)際組合學(xué)界的廣泛重視。歷史上，人們對(duì)覆蓋的研究興趣主要集中在它們的優(yōu)化問題上。特殊的覆蓋可以導(dǎo)出圖的一些良好的性質(zhì)，鑒于這類問題在實(shí)際應(yīng)用中的價(jià)值，此類研究近期應(yīng)用于圖的結(jié)構(gòu)性之上。事實(shí)表明，許多覆蓋問題在組合優(yōu)化理論、編碼理論、計(jì)算幾何、計(jì)算機(jī)圖形學(xué)、結(jié)晶學(xué)及運(yùn)籌學(xué)等領(lǐng)域都有十分重要的意義和廣闊的應(yīng)用前景，在網(wǎng)絡(luò)設(shè)計(jì)中也能發(fā)揮其重要的應(yīng)用價(jià)值。覆蓋問題有很多種，在生活的各個(gè)領(lǐng)域都發(fā)揮著舉足輕重的作用，比如在通信行業(yè)，基于覆蓋問題的研究基礎(chǔ)，可以簡(jiǎn)化通信網(wǎng)絡(luò)的層次分布與優(yōu)化；通過對(duì)覆蓋圖案的分析，可以運(yùn)用CAD軟件繪制出各種美感的圖形；在醫(yī)學(xué)和化學(xué)等行業(yè)，物質(zhì)分子結(jié)構(gòu)的構(gòu)造也會(huì)涉及到覆蓋問題的相關(guān)理論?？傊?，對(duì)此類問題的研究可以引起相關(guān)學(xué)者對(duì)此類研究問題的廣泛關(guān)注與興趣，從而促使覆蓋理論的不斷完善與豐富。等可覆蓋問題就是其中的重要研究?jī)?nèi)容，它作為覆蓋問題中一個(gè)活躍的分支，起源于Caro與Schonheim對(duì)P3-可分解圖特征的刻畫，具有重要的理論意義和實(shí)際意義。

1 研究背景與基本定義

1.1 研究背景

覆蓋問題是理論計(jì)算機(jī)科學(xué)中一類非常重要而又基本的問題。在美國(guó)的貝爾實(shí)驗(yàn)室、普林斯頓大學(xué)等一些重要的研究機(jī)構(gòu)，有許多專家在從事這方面的研究。1985年，S.Ruiz引入了隨機(jī)H-可分解圖的概念，并刻劃了H分別為p3和M2時(shí)的隨機(jī)H-可分解圖的特征。作為隨機(jī)H-可分解性的放松，數(shù)學(xué)家B.L.Harthell和P.D.Vestergaard引入H-等可填充圖的概念，并刻劃了圍長(zhǎng)大于等于5的H-等可填充圖的特征。接下來，B.Randerath和P.D.Vestergaard給出了所有H-等可填充圖的特征。2008年，Zhang引出H-等可填充圖的對(duì)偶的概念：H-等可覆蓋圖的概念，并完全刻劃了H-等可覆蓋圖的特征。2009年，Zhang等給出了M2-等可覆蓋圖的一些結(jié)論，并刻畫了幾類特殊的M2-等可覆蓋圖，并已完全刻畫了M2-等可覆蓋圖的特征。在本文中，我們給出所有含4-圈且不含3-圈的P4-等可覆蓋圖的刻畫。

1.2 基本定義

令H為某一固定的圖。如果圖G的每一條邊都至少出現(xiàn)在某一個(gè)子圖Hi（i=1，2，…k中，即，則稱為G的一個(gè)H-覆蓋。設(shè)為圖G的一個(gè)H-覆蓋，若對(duì)于任意Hj（j∈{l，2，3，…k}），均不是G的一個(gè)覆蓋，則稱為G的一個(gè)極小H-覆蓋。設(shè)H1，H2，…Hk為G的一個(gè)H-覆蓋，如果不存在少于k個(gè)同構(gòu)于H的子圖可以覆蓋圖G，則稱H，H2，…Hk為G的一個(gè)最小H-覆蓋。如果G的每個(gè)極小H-覆蓋都是G的最小H-覆蓋，則稱G為H-等可覆蓋的。我們用MG（L）表示G的一個(gè)極小H-覆蓋L=H1，H2，…Hk的覆蓋數(shù)，用mG（L）表示G的最小H-覆蓋的覆蓋數(shù)。

命題 1.1 一個(gè)連通圖G是P4-可覆蓋的當(dāng)且僅當(dāng)它有一個(gè)子圖P4。

顯然，如果一個(gè)連通圖G是P4-可覆蓋的，它至少含有3條邊。注意到當(dāng)G同構(gòu)于K1，t（t>3），那么它不是P4-可覆蓋的。所以在下文中描述的階數(shù)大于等于4的P4-可覆蓋圖中，不含有K1，t（t>3）。

命題 1.2 一個(gè)圖G是P4-可覆蓋的當(dāng)且僅當(dāng)它的每一個(gè)連通分支都是P4-可覆蓋的。

引理 1.3G是一個(gè)連通圖。如果G可以分解為幾個(gè)連通的P4-可覆蓋圖，且它們中的至少一個(gè)不是P4-等可覆蓋的，那么G不是P4-等可覆蓋的。

引理 1.4G是一個(gè)樹。我們將G中不相鄰的兩點(diǎn)合并為一點(diǎn)從而得到了一個(gè)含圈的新圖G。如果G不是P4-等可覆蓋的，那么G不是P4-等可覆蓋的。

2 主要結(jié)論

首先，我們刻畫了p4-等可覆蓋的路和圈。

引理 2.1 路Pn是P4-等可覆蓋的當(dāng)且僅當(dāng)n=4，5，6，7，8，11.

引理 2.2 圈Cn是P4-等可覆蓋的當(dāng)且僅當(dāng)n=4，5，7.

下面，我們給出一個(gè)有用的結(jié)論。

定義 2.3 對(duì)于星Ki，t，我們將其中度為k的結(jié)點(diǎn)稱為中心結(jié)點(diǎn)，其他結(jié)點(diǎn)稱為端點(diǎn)（樹葉）。在星K1，t的每條邊上都插入一個(gè)2度結(jié)點(diǎn)所得的樹稱為一個(gè)k-擴(kuò)星。即k-擴(kuò)星有一個(gè)度k結(jié)點(diǎn)（稱為擴(kuò)星的中心），k個(gè)度2結(jié)點(diǎn)，k片樹葉。我們記之為在k-擴(kuò)星的每條邊上都插入一個(gè)2度結(jié)點(diǎn)所得的樹稱為一個(gè)二階k-擴(kuò)星，記之為類似地，n階k-擴(kuò)星是通過在n-l階k-擴(kuò)星的每條邊上都插入一個(gè)2度結(jié)點(diǎn)所得到的。

下面的引理很容易驗(yàn)證是正確的：

引理 2.4 每一個(gè)二階k擴(kuò)星都是P4-等可覆蓋的。

注釋 2.5 顯然，P4可以表示為而P7可以表示為.

引理 2.6 G是一個(gè)連通圖且非圈。如果G不含3-圈且含有4-圈，那么G不是P4-等可覆蓋的，除非G是（n>l）或者G是由n個(gè)P2·K1，t（t>3）中p2部分的度1結(jié)點(diǎn)與C4中的同一個(gè)結(jié)點(diǎn)合并而構(gòu)成的圖。

證明：情形1：G是由若干個(gè)p2和C4合并而成的圖。

（1）如果C4的每一個(gè)結(jié)點(diǎn)只能與至多一個(gè)P2的端點(diǎn)合并，那么G只可能是圖1中的五種情況之一。對(duì)于圖1中的每一個(gè)圖，我們都可以找到一個(gè)極小覆蓋L，使得它的覆蓋數(shù)MG（L）大于最小覆蓋的覆蓋數(shù)m （G）。所以圖1中的圖都不是P4-等可覆蓋的。

（2）如果C4的每一個(gè)結(jié)點(diǎn)可以與多個(gè)p2的端點(diǎn)合并，那么G可以看作是由多個(gè)P2的端點(diǎn)與G中的4-圈部分的結(jié)點(diǎn)合并而成，其中G為圖1中的圖之一。如果p2的數(shù)目為n，我們可以找到一個(gè)覆蓋數(shù)為M（G）+n的極小P4覆蓋（用M（G）個(gè)P4覆蓋G部分，用n個(gè)P4覆蓋其余部分），而最小覆蓋的覆蓋數(shù)不會(huì)多于m（G）+n。對(duì)于每一個(gè)G，都存在一個(gè)它的極小覆蓋，其覆蓋數(shù)M（G）>m（G），因此G不是P4-等可覆蓋的。

情形 2：G是由若干個(gè)P3和C4合并而成的圖。

注意到我們是將每一個(gè)P3的端點(diǎn)而不是中心點(diǎn)與C4的結(jié)點(diǎn)合并，否則的話G就與情形1中的某些圖重復(fù)了。

（1）如果C4的每一個(gè)結(jié)點(diǎn)只能與至多一個(gè)P3的端點(diǎn)合并，那么G只可能是圖2中的五種情況之一，對(duì)于圖2中的每一個(gè)圖，我們都可以找到一個(gè)極小覆蓋L，使得它的覆蓋數(shù)MG（L）大于最小覆蓋的覆蓋數(shù)m（G）。所以圖2中的圖都不是P4-等可覆蓋的。

（2）如果C4的每一個(gè)結(jié)點(diǎn)可以與多個(gè)P2的端點(diǎn)合并，那么G可以看作是由多個(gè)P2的端點(diǎn)與G中的4-圈部分的結(jié)點(diǎn)合并而成，其中G為圖2中的圖之一。如果P2的數(shù)目為n，我們可以找到一個(gè)覆蓋數(shù)為M（G）+n的極小P4覆蓋（用M（G）個(gè)P4覆蓋G部分，用n個(gè)P4覆蓋其余部分），而最小覆蓋的覆蓋數(shù)不會(huì)多于m（G）+n。對(duì)于每一個(gè)G，都存在一個(gè)它的極小覆蓋，其覆蓋數(shù)M（G）>m（G），因此G不是P4-等可覆蓋的。

情形 3：G是由若干個(gè)P2和若干個(gè)P3與C4合并而成的圖。

如果只有若干個(gè)P2或者若干個(gè)P3，那么與情形1或情形2相同。否則，

（1）如果C4的每一個(gè)結(jié)點(diǎn)只能與至多一個(gè)P2或P2的端點(diǎn)合并，那么G只可能是圖3中的九種情況之一。對(duì)于圖3中的每一個(gè)圖，我們都可以找到一個(gè)極小覆蓋L，使得它的覆蓋數(shù)MG（L）大于最小覆蓋的覆蓋數(shù)m（G）。所以圖3中的圖都不是P4-等可覆蓋的。

（2）如果C4的每一個(gè)結(jié)點(diǎn)可以與多個(gè)P2或P2的端點(diǎn)合并，那么G可以看作是由多個(gè)P2或P3的端點(diǎn)與G中的4-圈部分的結(jié)點(diǎn)合并而成，其中G為圖2中的圖之一。如果p2和P3的總數(shù)目為n，我們可以找到一個(gè)覆蓋數(shù)為M（G）+n的極小P4覆蓋（用M（G）個(gè)P4覆蓋G部分，用n個(gè)P4覆蓋其余部分），而最小覆蓋的覆蓋數(shù)不會(huì)多于m（G）+n。對(duì)于每一個(gè)G，都存在一個(gè)它的極小覆蓋，其覆蓋數(shù)M（G）>m（G），因此G不是P4-等可覆蓋的。

（3）容易驗(yàn)證，圖4中的圖不是P4-等可覆蓋的。如果C4中的一個(gè)或多個(gè)結(jié)點(diǎn)與至少一個(gè)P，和一個(gè)P2的端點(diǎn)合并，那么G可分解為兩部分： P4和一個(gè)非P4-等可覆蓋的圖。

情形4：G是由若干個(gè)星K1，t（t>3）和C4合并而成的圖。

注意到我們是將每一個(gè)星K1，t（t>3）的端點(diǎn)而不是中心點(diǎn)與C4的結(jié)點(diǎn)合并，否則的話G就與情形1中的某些圖重復(fù)了。

當(dāng)t=3時(shí)，

（1）如果C4的每一個(gè)結(jié)點(diǎn)只能與至多一個(gè)星K1，（t>3）的端點(diǎn)合并，那么只可能得到5個(gè)可能的圖。容易驗(yàn)證這5個(gè)圖都不是P4-等可覆蓋的。

（2）如果C4的每一個(gè)結(jié)點(diǎn)可以與多個(gè)P2或P3的端點(diǎn)合并，那么G可以分解為n個(gè)K1，t和一個(gè)圖G，其中圖G是（1）中一個(gè)非P4-等可覆蓋的圖。記G的一個(gè)極小P4覆蓋的覆蓋數(shù)為M（G），那么圖G存在一個(gè)覆蓋數(shù)為M（G）+n的極小P4覆蓋，而圖G的最小P4覆蓋的覆蓋數(shù)不會(huì)大于m（G）+n.于是G不是P4-等可覆蓋的。

當(dāng)t >4時(shí)，我們可以找到G的一個(gè)極小P4覆蓋，其覆蓋數(shù)為M（G-）+（t一3）>m（G-）+（t-3）（用M（G）個(gè)P4覆蓋G-部分，用（t-3）個(gè)P4覆蓋其余部分）。而圖G的最小P4覆蓋的覆蓋數(shù)不會(huì)大于m（G）+n.于是G不是P4-等可覆蓋的。

情形 5：G是由若干個(gè)p2和若干個(gè)K1，t（t>3）與C4合并而成的圖。

注意到我們是將每一個(gè)星K1，t（t>3）的端點(diǎn)而不是中心點(diǎn)與C4的結(jié)點(diǎn)合并。如果只有若干個(gè)p2或者若干個(gè)K1，t（t>3），那么與情形1或情形4相同。否則，

當(dāng)t=3時(shí)，

（1）如果C4的每一個(gè)結(jié)點(diǎn)只能與至多一個(gè)P，或K1，3的端點(diǎn)合并，那么G只可能是圖5中的九種情況之一。對(duì)于圖5中的每一個(gè)圖，我們都可以找到一個(gè)極小覆蓋L，使得它的覆蓋數(shù)MG （L）大于最小覆蓋的覆蓋數(shù)m（G）。所以圖5中的圖都不是P4-等可覆蓋的。

（2）如果C。的每一個(gè)結(jié)點(diǎn)可以與多個(gè)P，或K1，t的端點(diǎn)合并，那么G可以看作是由多個(gè)P2或K1，3的端點(diǎn)與G中的4-圈部分的結(jié)點(diǎn)合并而成，其中G為圖5中的圖之一。如果P，和K1，3的總數(shù)目為n，我們可以找到一個(gè)覆蓋數(shù)為M（G）+n的極小P4覆蓋（用M（G）個(gè)P4覆蓋G部分，用n個(gè)P4覆蓋其余部分），而最小覆蓋的覆蓋數(shù)不會(huì)多于m （G）+n。對(duì)于每一個(gè)G，都存在一個(gè)它的極小覆蓋，其覆蓋數(shù)M（G）>m（G），因此G不是P4-等可覆蓋的。

（3）我們將圖6中的圖記為G。由于存在一個(gè)極小覆蓋，其覆蓋數(shù)M（G）=4>3=m（G），所以G不是P4-等可覆蓋的。如果C4的一個(gè)或多個(gè)結(jié)點(diǎn)與至少一個(gè)P2和K1，3合并，那么G可以被分解為兩部分：P2和一個(gè)非P4-等可覆蓋圖。

當(dāng)t >4時(shí)，我們可以找到G的一個(gè)極小P4覆蓋，其覆蓋數(shù)為M（G）+（t-3）>m （G）+（t-3）（用M（G）個(gè)P4覆蓋G部分，用（t-3）個(gè)P4覆蓋其余部分）。而圖G的最小P4覆蓋的覆蓋數(shù)不會(huì)大于m（G）+n.于是G不是P4-等可覆蓋的。

情形 6：G是由若干個(gè)P2和若干個(gè)K1，t（t>3）與C4合并而成的圖。

注意到我們是將每一個(gè)星K1，t（t>3）的端點(diǎn)而不是中心點(diǎn)與C4的結(jié)點(diǎn)合并。如果只有若干個(gè)P3或者若干個(gè)K1，t（t>3），那么與情形2或情形4相同。否則，

與情形5類似，G不是P4-等可覆蓋的。

情形 7：G是由若干個(gè)P2，P3和若干個(gè)K1，t（t>3）與C4合并而成的圖。

注意到我們是將每一個(gè)星Kl，t（t>3）的端點(diǎn)而不是中心點(diǎn)與C4的結(jié)點(diǎn)合并。我們只需要考慮若干個(gè)P2，P3和若干個(gè)K1，t（t>3）同時(shí)與C4合并的情形。否則，G與之前情形中的某些圖相同。

與情形5類似，G不是P4-等可覆蓋的。

情形8：G是由若干個(gè)P4和C4合并而成的圖。

注意到我們是將每一個(gè)P4的端點(diǎn)與C4的結(jié)點(diǎn)合并，否則的話G就與之前情形中的某些圖重復(fù)了。

（1）如果n個(gè)P4的端點(diǎn)只能與C4的一個(gè)結(jié)點(diǎn)合并，那么極小覆蓋數(shù)MG（L）和最小P4覆蓋數(shù)m（G）都是n+2。我們將這個(gè)圖記作，它是P4-等可覆蓋的。

（2）如果n個(gè)P4的端點(diǎn)可以與C4的至少兩個(gè)結(jié)點(diǎn)合并，那么存在一個(gè)覆蓋數(shù)MG（L）=n+3的極小P4覆蓋，而最小P4覆蓋數(shù)m（G）是n+2，因?yàn)镸G（L）>m（G），所以G不是P4一等可覆蓋的。

情形9：G是由若干P2K1，t（t>3）和C4合并而成的圖。

我們將P2的一個(gè)端點(diǎn)與K1，t（t>3）的一個(gè)端點(diǎn)合并得到的圖記作P2·K1，t（t>3）。我們將P2.K1，t（t>3）中的P2部分的端點(diǎn)與C4的結(jié)點(diǎn)合并，否則G就與之前情形中的某些圖重復(fù)了。

（1）如果n個(gè)P2·K1，t（t>3）只能與C4的一個(gè)結(jié)點(diǎn)合并，那么極小覆蓋數(shù)MG （L）和最小P4覆蓋數(shù)m（G）都是n（t-l）+2。它是P4-等可覆蓋的。

（2）如果n個(gè)P2·Kl·t（t>3）可以與C4的至少兩個(gè)結(jié)點(diǎn)合并，那么存在一個(gè)覆蓋數(shù)MG（L）=n（t-1）+3的極小P4覆蓋，而最小P4覆蓋數(shù)m（G）是n（t-1）+2，因?yàn)镸G（L）>m（G），所以G不是P4-等可覆蓋的。

情形10：G不屬于情形1-9。

每一個(gè)圖G可以被分解為2個(gè)連通的部分：一個(gè)包含于情形1-9中的非P4-等可覆蓋圖和一個(gè)P4-可覆蓋圖。由引理1.4，G不是P4-等可覆蓋的。

綜上，G不是P4-等可覆蓋的，除非G是C4·Sn2*（n>l）或者是由n個(gè)P2·Kl，t（t>3）與C4的同一個(gè)結(jié)點(diǎn)合并而成的圖。