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

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

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

3、的區(qū)組．最大的填充設(shè)計(jì)( 最小的覆蓋設(shè)計(jì)) 的區(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 ．為了敘述簡(jiǎn)潔，我們稱填充數(shù)為礦( ”，G ，A )

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

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

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