圖的全染色以及鄰點(diǎn)可區(qū)別全染色.pdf

1、具有重要的理論意義和實(shí)用價(jià)值的各種染色問(wèn)題，一直是圖論中的熱點(diǎn)話題之一。離散系統(tǒng)、組合分析中的許多問(wèn)題都可轉(zhuǎn)化為圖著色問(wèn)題，例如，不含給定圖G作為子圖的n個(gè)頂點(diǎn)的圖的邊的最大數(shù)目就依賴于G的色數(shù)。因此TR.Jensen和B.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ù)分配等等，都與圖著色理論密

2、切相關(guān)，也正是圖著色理論的實(shí)際應(yīng)用才引起了世人的興趣。 所謂圖著色是指對(duì)圖中的頂點(diǎn)、邊(對(duì)平面圖而言還有面)等元素按照一定的規(guī)則進(jìn)行分類。對(duì)象不同或規(guī)則不同，便有各式各樣的著色，繼圖的點(diǎn)著色、邊著色以及組合地圖的面著色之后，人們又提出了全色數(shù)的概念。如點(diǎn)著色、邊著色、全著色、強(qiáng)染色、鄰強(qiáng)邊著色、鄰點(diǎn)可區(qū)別全染色、點(diǎn)可區(qū)別邊染色、邊面著色、完美著色等成百上千種著色方式。 為了恰當(dāng)?shù)乇硎敬笮统W(wǎng)絡(luò)、存儲(chǔ)問(wèn)題、時(shí)間安排和任務(wù)分

3、配等研究課題中各元素之間的關(guān)系，圖的染色理論做為一種可行的工具被自然的引入。由于其良好的應(yīng)用背景，圖的染色理論已成為現(xiàn)在圖論領(lǐng)域中迅速發(fā)展的子學(xué)科之一。 本論文首先綜述了全染色的基本概念和研究現(xiàn)狀，然后統(tǒng)一各種文獻(xiàn)中有關(guān)染色的概念。文章根據(jù)全著色理論得出了若干圖的全色數(shù)，并通過(guò)對(duì)這些圖的全色數(shù)的確定驗(yàn)證全著色猜想(TCC)，得出了全著色方面的一些定理，在全著色的實(shí)際應(yīng)用中，給出了某些圖的全著色算法。 其次，文章引入鄰點(diǎn)可