圖的BBC染色.pdf

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

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

3、個映射，：v(c)一1，2，，七)，滿足(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)=七近年來，圖的染色概念不斷演化，出現(xiàn)了很多與頻率分配相關(guān)的染色如：L(2，1)一標號染色。距離2一染色，Radio一染色等概念BBC染色概念最早由日町oBroersma教授在第29屆國