圖的BBC染色.pdf

1、li啃p◆霹?！k17搿：辯●圖的BBC染色TheBackboneColoringofGraphsi、作者旦蘭指導(dǎo)教師I月華學(xué)位類(lèi)別學(xué)科專(zhuān)業(yè)理學(xué)碩士應(yīng)用數(shù)學(xué)學(xué)位授予單位浙江師范大學(xué)論文提交日期2010年5月25日^口蔣P，■I，t，：0‘飛v，。、，H0I；Ⅶ『，l崞√，二一●7I▲■圖白gBBC染色lIIIIIIIIIIIIIIIllllllllIIl＼1804385摘要一個(gè)有序?qū)=(VE)稱(chēng)為一個(gè)無(wú)向圖，其中y是一個(gè)有限集合，E是

2、y中的不同元素的無(wú)序?qū)Φ募蟳中的元素叫做圖G的頂點(diǎn)，E中的元素叫做圖G的邊通常用y(G)，E(C)分別表示圖G的頂點(diǎn)集合與邊集合沒(méi)有重邊和環(huán)的圖叫做簡(jiǎn)單圖圖G的一個(gè)正常k頂點(diǎn)染色是指一個(gè)映射毋：V一1，，七)，使得對(duì)任意tIt，∈E(G)，滿(mǎn)足咖(tI)≠≯(u)若圖G有一個(gè)正常k點(diǎn)染色，那么就稱(chēng)圖G是k點(diǎn)可染色的圖G的色數(shù)是指G有一個(gè)正常k頂點(diǎn)染色的數(shù)七的最小值，用x(C)表示令Ⅳ是G的生成子圖，(G，日)的一個(gè)BBC一七一染色是一

3、個(gè)映射，：v(c)一1，2，，七)，滿(mǎn)足(1)若u“∈E(H)，則l，(u)一，(u)I≥2；(2)若uu∈E(G)＼E(日)，則I，(tt)一fCv)I≥1(G，H)的BBC染色數(shù)就是指最小的整數(shù)七，使得(G，Ⅳ)有BBC一七一染色，記作Xb(C，H)=七近年來(lái)，圖的染色概念不斷演化，出現(xiàn)了很多與頻率分配相關(guān)的染色如：L(2，1)一標(biāo)號(hào)染色。距離2一染色，Radio一染色等概念BBC染色概念最早由日町oBroersma教授在第29屆國(guó)