若干圖類的鄰強邊染色與2-強邊染色問題研究.pdf

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

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

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