圖與超圖的帶寬和問(wèn)題.pdf

1、浙江師范大學(xué)碩士學(xué)位論文圖與超圖的帶寬和問(wèn)題姓名：黃丹君申請(qǐng)學(xué)位級(jí)別：碩士專業(yè)：應(yīng)用數(shù)學(xué)指導(dǎo)教師：卜月華20040501定理5 對(duì)于n 階線性超圖日= ㈣，島，?，％) ，有mB s ( 月’) ≥壚( m ，∑I 墨l —n ) 。i = 12 ．圖帶寬和與其對(duì)偶超圖帶寬和的關(guān)系為討論方便起見，在第三章里引進(jìn)邊帶寬和的概念。給定一個(gè)有限集x 上的超圖日= ( 毋，易，?，％) ，其中閣= n 。任意一個(gè)雙射g ：日- ÷{

2、1 ，2 ，?m ) 稱為超圖日的一個(gè)邊標(biāo)號(hào)。對(duì)超圖日的一個(gè)邊標(biāo)號(hào)9 及且的任一個(gè)點(diǎn)茁，定義函數(shù)口∽( 囂) ) = m a z 伽( 最) 一g ( 馬) 1 | 廄，馬∈日( z ) } ，稱日y ㈣g ) = ∑9 ( 日( z ) ) 為超圖日的關(guān)于邊標(biāo)號(hào)9 的邊帶寬和，稱B ∥( 日) = m i n { B 剛?cè)眨? ) b 是超圖日的邊標(biāo)號(hào)) 為超圖日的邊帶寬和，并稱使日s ，( 日) 達(dá)到最小的邊標(biāo)號(hào)9 為超圖日的一個(gè)最

3、優(yōu)邊標(biāo)號(hào)。定理6 設(shè)超圖日·= ( x 1 ，％，?，％) 是超圖日= ( E l ，場(chǎng)，?，‰) 的對(duì)偶超圖，則B s ( 日+ ) = 口∥( 日) 。對(duì)一般圖G ，B s ( G ) 與B s ( G + ) 的大小關(guān)系是不確定的。但當(dāng)G 是森林或單圈圖時(shí)，我們有下述結(jié)果。定理7 設(shè)T 是森林，則日s ( P ) ≤B s ( T ) 。定理8 設(shè)G 是一個(gè)單圈圖，則曰s ( ∥) ≤B s ( G ) 。3 ．超圖帶寬

4、和的某些下界由于超圖帶寬和問(wèn)題是N P ．完全的，于是人們通過(guò)以下兩種途徑擴(kuò)充其結(jié)果： 1 、尋求超圖帶寬和問(wèn)題的近似算法或啟發(fā)式算法；2 、求B s ( 日) 的上下界來(lái)確定某些特殊超圖的帶寬和。在第四章里利用超圖日的度序列給出口s ( 日) 的一個(gè)下界并建立了帶寬和問(wèn)題的H a 印e r 型下界估計(jì)式，由此得到一系列特殊超圖的帶寬和。定理9 設(shè)序列( d ，，屯?，如) 是n 一致超圖日的度序列p ≥2 ) ，m為超圖日的邊數(shù)。令％