幾類等可填充與等可覆蓋問題的研究.pdf

1、填充與覆蓋問題是圖論的主要研究內(nèi)容之一，在網(wǎng)絡(luò)設(shè)計、組合優(yōu)化理論、結(jié)晶學(xué)及運(yùn)籌學(xué)等領(lǐng)域都有十分重要的意義。填充和覆蓋是圖的一對具有對偶性質(zhì)的概念，對研究圖的結(jié)構(gòu)性質(zhì)也具有重要的意義。圖論中的填充與覆蓋問題有多種，本論文研究了其中互為對偶的一類：H-等可填充圖與H-等可覆蓋圖的特征刻劃問題。設(shè)Hi，H2，…，Hl為圖G的一個H-填充，若G-∪(i=1,l)E(Hi)不含同構(gòu)于H的子圖，則稱Hi，H2，…，Hl為G的一個極大H-填充。若G中

2、不存在多于l個同構(gòu)于H的兩兩不交的子圖，則稱H1，H2，…，Hl為G的一個最大H-填充。若G的每個極大H-填充都是它的最大H-填充，則稱G為H-等可填充的。設(shè)Hi，H2，…，Hl為G的一個H-覆蓋，若對于任意Hj(j∈{1，2，…，l}），∪(i≡1,l)E(Hi)-E(Hj)都不是G的一個覆蓋，則稱H1，H2，…，Hl為G的一個極小覆蓋。若不存在少于l個同構(gòu)于H的子圖可覆蓋G，則稱H1，H2，…，Hl為G的一個最小H-覆蓋。若G的每個

3、極小H-覆蓋都是G的最小H-覆蓋，則稱G為H-等可覆蓋的。P3-等可填充圖、M2-等可填充圖、P3-等可覆蓋圖和M2-等可覆蓋圖的特征已經(jīng)被刻劃。本論文首先在M3-可分解圖、隨機(jī)M3-可分解圖及M2一等可填充圖的研究基礎(chǔ)上，完全刻劃了M-等可填充圖的特征。然后刻劃了Mk-等可填充的路和圈，Pk-等可填充的路和圈，及Pm∪Pk-等可填充的路和圈的特征。最后刻劃了Mk-等可覆蓋的路和圈，Pk-等可覆蓋的路和圈，及Pm∪Pk-等可覆蓋的路和圈