圖的染色理論是圖論研究的熱點(diǎn)問題之一.而均勻染色理論又是染色理論的進(jìn)一步發(fā)展,在化學(xué)、生物學(xué)、計(jì)算機(jī)科學(xué)、工業(yè)生產(chǎn)和企業(yè)管理等領(lǐng)域中有著廣泛的應(yīng)用.圖的團(tuán)染色是圖的點(diǎn)染色的一個(gè)變體,又稱之為弱染色.本文主要研究的是圖的團(tuán)染色問題和圖的均勻團(tuán)染色問題.研究圖的團(tuán)染色問題和圖的均勻團(tuán)染色問題有著重要的應(yīng)用背景和理論價(jià)值.第一章首先闡述了本文所需要的基本概念和定義.其次介紹了本課題的研究意義.最后對(duì)近十幾年團(tuán)染色的研究進(jìn)展做了系統(tǒng)的梳理.第二章主要研究了平面圖的團(tuán)染色問題.Mohar和ˇkrekovski已證明了平面圖是3-團(tuán)可染色的(Electr.J.Combin.6（1999）,#R26).在本章節(jié)中,我們運(yùn)用歸納法進(jìn)一步證明了任意平面圖是3-團(tuán)可染色的,并且設(shè)計(jì)了一個(gè)3-團(tuán)染色平面圖的線性時(shí)間算法（以上結(jié)果已經(jīng)發(fā)表在《Operations Research Letters》雜志）.第三章主要研究了無爪圖的均勻團(tuán)染色問題.Bacs′o和Tuza證明了以下定理:除了階數(shù)大于3的無弦奇圈,最大度至多為4的無爪連通圖是2-團(tuán)可染色的,并且在（9）²)時(shí)間內(nèi)可以找到一個(gè)2-團(tuán)...

【文章頁數(shù)】：41 頁

【學(xué)位級(jí)別】：碩士

【文章目錄】：
摘要
Abstract
符號(hào)表
第一章 緒論
    1.1 基本概念與定義
    1.2 課題介紹及研究意義
    1.3 團(tuán)染色問題的研究進(jìn)展
第二章 平面圖的團(tuán)染色問題
    2.1 平面圖的團(tuán)染色
    2.2 線性時(shí)間算法
第三章 無爪圖的均勻團(tuán)染色問題
    3.1 無爪圖的均勻團(tuán)染色
    3.2 線性時(shí)間算法
    3.3 結(jié)論
參考文獻(xiàn)
攻讀碩士學(xué)位期間完成及發(fā)表的論文
致謝



本文編號(hào)：4034031