帶一條懸邊的K-,1-與C-,4-聯(lián)圖的填充與覆蓋.pdf

1、河北師范大學(xué)碩士學(xué)位論文帶一條懸邊的K與C聯(lián)圖的填充與覆蓋姓名：劉曉姍申請學(xué)位級別：碩士專業(yè)：應(yīng)用數(shù)學(xué)指導(dǎo)教師：康慶德20050501河北師范大學(xué)碩士論文1 引言本文分為兩個部分：第一部分研究兩個六點(diǎn)九邊圖G 與Q 的填充設(shè)計和覆蓋設(shè)計．第二部分研究圖w ( m ，，z ) 的邊優(yōu)美指標(biāo)集問題，1 ．1 圖的填充與覆蓋設(shè)計設(shè)^ 凰是A 重口點(diǎn)完全圖，其任二不同頂點(diǎn)x 和Y 問都恰有A 條邊( x ，Y ) 相連．對于有限簡單圖G ，所謂

2、的G 一圖設(shè)計G —G D A ( v ) ( G 一填充設(shè)計G —P D ^ ( “ ) ，G 一覆蓋設(shè)計G —C D ^ ( 口) ) ，是一個序偶( x ，B ) ，其中x 是K ，的頂．占、集，8 為凰中同構(gòu)干G 的子圖的集合( 稱為區(qū)組集) ，使得％中每條邊恰好( 至多，至少) 出現(xiàn)在t 3 的A 個區(qū)組中．一個填充設(shè)計( 覆蓋設(shè)計) 被稱為最大( 最小) 的是指不再存在其它同階數(shù)的填充設(shè)計( 覆蓋設(shè)計) 含有更多( 更少)

3、的區(qū)組．最大的填充設(shè)計( 最小的覆蓋設(shè)計) 的區(qū)組數(shù)稱為填充數(shù)( 覆蓋數(shù)) ，記作p ( 口，G ，A ) ( c 扣，G ，^ ) ) ．顯然，p 一，G ，A ) ≤u o ，G ，A ) = 【；箍耥J ≤『高害每井] = y o ，G ，^ ) ≤c ( ”，G ，^ ) ( + )這里l 。J ( 『。] ) 分別表示滿足Y ≤∞( Y ≥z ) 的最大( 最小) 整數(shù)Y ．為了敘述簡潔，我們稱填充數(shù)為礦( ”，G ，A )

4、的填充設(shè)計( 覆蓋數(shù)為y ( “ ，G ，A ) 的覆蓋設(shè)計) 為正則的，簡記為G —O P D ^ ( v ) ( G 一0 G D ^ ( u ) ) ．顯然，圖設(shè)計G —G D x ( v ) 存在當(dāng)且僅當(dāng)p ( u ，G ，A ) =c ( 。，G ，n 因此，一個圖設(shè)計G ．G D z ( ”) 可看成是正則的填充設(shè)計或正則的覆蓋設(shè)計．一個填充設(shè)計G ．P D ) I ( v ) = ( K P ) 的余邊圖以( P ) 是^

5、 凰的子圖，它的邊集是P( 視為填充設(shè)計中各區(qū)組所對應(yīng)子圖的多重并) 在^ 虬中的補(bǔ)．當(dāng)P 最大時，Ik ( P ) I稱為此填充設(shè)計的余邊數(shù)，記作h ( “ ) ．類似地，一個覆蓋設(shè)計G ．C D ^ ( v ) = ( K C ) 的重邊圖R ^ ( c ) 也是A 凰的子圖，它的邊集是A 凰在c ( 視為覆蓋設(shè)計中各區(qū)組所對應(yīng)子圖的多重并) 中的補(bǔ)．當(dāng)C 最小時，I “( c ) l 稱為此覆蓋設(shè)計的重邊數(shù)，記作，- ^ ∞) ．

6、為簡便起見，_ L ^ ( P ) 與t a ( v ) 通常簡記為L ^ 與h ，而R ^ ( c ) 與n 扣) 則簡記為R ^ 與n稱A ‰。，。。，。。= ( U 咒，日) 為一個A 重完全多部圖，其中諸五兩兩不相交，{ x i l = m ，且對于V x ∈墨，Y ∈瑪，邊( 。，Y ) 在E 中出現(xiàn)^ 次( 當(dāng)i ≠j 對) 或不出現(xiàn)( 當(dāng)i = ，時) ，圖G 的型為T = n 1 1 ¨2 1 ·-