發(fā)布時間：2025-02-13 19:53

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

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

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

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



本文編號：4034031