若干圖類的鄰強(qiáng)邊染色與2-強(qiáng)邊染色問(wèn)題研究.pdf

1、分類號(hào)UDC密級(jí)單位代碼10151若干圖類的鄰強(qiáng)邊染色與2一強(qiáng)邊染色問(wèn)題研究席美麗指導(dǎo)教師王德強(qiáng)職稱教授學(xué)位授予單位大連海事大學(xué)申請(qǐng)學(xué)位級(jí)別碩十學(xué)科與專業(yè)應(yīng)用數(shù)學(xué)論文完成日期2008.5.20論文答辯日期2008.6.28答辯委員會(huì)主席中文摘要摘要具有重要的理論意義和實(shí)際意義的各種染色問(wèn)題，一直是圖論中的熱點(diǎn)話題之一離散系統(tǒng)中的許多問(wèn)題都可以轉(zhuǎn)化為圖著色問(wèn)題，例如，給定圖G，不包含子圖的G的n個(gè)頂點(diǎn)的圖的邊的最大數(shù)目就依賴于圖G的色數(shù).

2、因此Jensen和Toft斷言:圖著色理論在離散數(shù)學(xué)中處于中心的地位.在現(xiàn)實(shí)生活中許多領(lǐng)域都會(huì)涉及到將某種對(duì)象的集合按照一定的規(guī)則進(jìn)行分類的問(wèn)題，例如時(shí)間表問(wèn)題、排序問(wèn)題、排課表問(wèn)題、存儲(chǔ)問(wèn)題、電路安排、任務(wù)分配等等，都與圖著色理論密切相關(guān).所謂圖著色是指對(duì)圖中的頂點(diǎn)、邊(對(duì)平面圖而言還有面)等元素按照一定的規(guī)則進(jìn)行分類.對(duì)象不同或規(guī)則不同，便有各式各樣的著色.隨著染色理論的發(fā)展又出現(xiàn)了許多新的染色，例如:全著色、列表著色、點(diǎn)強(qiáng)全著色、

3、強(qiáng)邊著色、強(qiáng)著色、關(guān)聯(lián)著色、圈著色、距離面著色、區(qū)間著色、r強(qiáng)邊著色、完備著色及動(dòng)態(tài)著色等，這些染色已成為現(xiàn)在圖著色領(lǐng)域中新的熱點(diǎn).對(duì)于過(guò)去很多未解決的問(wèn)題我們可以把它轉(zhuǎn)化為一個(gè)新的染色問(wèn)題，使原問(wèn)題變得簡(jiǎn)單易懂并且便于研究.本文主要研究的是圖的鄰強(qiáng)邊染色與2一強(qiáng)邊染色問(wèn)題.首先借助于Akbari對(duì)樹2一強(qiáng)邊染色及3一強(qiáng)邊染色的研究與張忠輔對(duì)樹鄰強(qiáng)邊染色的研究，給出了對(duì)樹進(jìn)行2一強(qiáng)邊染色時(shí)，2一強(qiáng)邊色數(shù)等于最大度加1的充分條件是具有最大