28939.圖的2距離著色問題的研究

1、圖的2距離著色問題的研究重慶大學(xué)碩士學(xué)位論文（學(xué)術(shù)學(xué)位）學(xué)生姓名：肖歡歡指導(dǎo)老師：謝德政教授專業(yè)：應(yīng)用數(shù)學(xué)學(xué)科門類：理學(xué)重慶大學(xué)數(shù)學(xué)與統(tǒng)計(jì)學(xué)院二O一四年四月重慶大學(xué)碩士學(xué)位論文中文摘要I摘要圖論是數(shù)學(xué)的一個(gè)重要分支，它為離散數(shù)學(xué)證明技巧的探索提供了極其豐富的背景，并且它的許多結(jié)果在計(jì)算科學(xué)、社會(huì)科學(xué)以及自然科學(xué)等方面有著廣泛的應(yīng)用。作為圖論研究的一個(gè)重要領(lǐng)域，圖的著色問題(即著色問題)也就成為了我們研究的一個(gè)目標(biāo)，它起源于著名的四色問題

2、。圖的著色理論不僅在組合分析和離散數(shù)學(xué)等數(shù)學(xué)問題的研究上有應(yīng)用，而且在其他領(lǐng)域也有非常重要的應(yīng)用，比如為了避免沖突合理安排考試及會(huì)議的日程問題，避免化學(xué)藥品相互反應(yīng)的安全存儲(chǔ)問題等。圖的著色問題的研究有著極其重要的意義。本文主要研究的是圖的2距離著色問題。它是建立在圖的正常的頂點(diǎn)著色的基礎(chǔ)之上的一種著色。本文具體內(nèi)容可分為以下四部分：第一部分(即第一章)介紹了圖論及其著色問題的起源發(fā)展及研究意義，并給出了本文所研究的內(nèi)容及目的。第二部分

3、(即第二章)主要給出了圖的著色問題中的一些基本概念，并著重介紹了圖的??Lpq標(biāo)號(hào)問題和2距離著色的概念，并對(duì)它們的研究現(xiàn)狀進(jìn)行了總結(jié)概括。第三部分(即第三、四章)本章是論文最重要的部分。在這一部分，重點(diǎn)探討了平面圖的2距離著色問題及若干特殊圖的2距離著色。第三章給出了某些非Hamilton圖的2距離著色，通過對(duì)這些具體圖的著色規(guī)律的分析，發(fā)現(xiàn)可以通過調(diào)換某些頂點(diǎn)顏色的著色方法將圖的部分著色進(jìn)行延拓。第四章，結(jié)合圖的2距離著色的特點(diǎn)，先