本文關(guān)鍵詞：圖的t-松弛染色問題研究

  更多相關(guān)文章： 染色 t-松弛染色 r-方路 r-方圈 k-樹 完全多部圖

【摘要】：圖的松弛染色問題來自于衛(wèi)星通信的頻率分配問題。設(shè)G(V,E)是一個(gè)圖,t是一個(gè)非負(fù)整數(shù)。令f是一個(gè)從頂點(diǎn)集V(G)到非負(fù)整數(shù)集的函數(shù),如果對(duì)任意頂點(diǎn)v都有|{u:f(u)=f(v),u ∈ V(G),uv ∈ E(G)}|≤則稱f是圖G的一個(gè)t-松弛染色。圖G的t-松弛色數(shù)記為χt(G),定義為minmax{f(v):v ∈ V(G)},其中f取遍圖G的所有t-松弛染色。本文主要考慮幾個(gè)特殊圖類的松弛染色問題。在第二章中,對(duì)任意非負(fù)整數(shù)t,我們確定了n個(gè)頂點(diǎn)的r-方路的t-松弛色數(shù),給出了n個(gè)頂點(diǎn)的r-方圈的t-松弛色數(shù)的上下界。當(dāng)t=0時(shí),χ0(G)即為圖G的正常色數(shù),即χ0(G)= χ(G)。顯然,當(dāng)t≥0時(shí),χt(G)≤χ(G)。第三章證明了在頂點(diǎn)數(shù)足夠多的情況下,kk-樹和每個(gè)部的頂點(diǎn)數(shù)為2t的完全多部圖的t-松弛色數(shù)等于它們的正常點(diǎn)色數(shù)。我們用K(n2,...,ns)表示一個(gè)完全s部圖,其中s個(gè)部的頂點(diǎn)數(shù)分別為n1,n2,...,n.s。在第四章中,對(duì)t = 1,2,3,4的情形,本文分別給出了求解K(n1,...,.s)的最優(yōu)t-松弛染色的多項(xiàng)式時(shí)間算法。按照相同的求解思路,可以得到t =5,6的最優(yōu)t-松弛染色的多項(xiàng)式時(shí)間算法,由于證明過程太長(zhǎng),故本文省略了這兩種情況的細(xì)節(jié)。當(dāng)t ≥ 7時(shí),因?yàn)轫旤c(diǎn)數(shù)的增多情況越來越復(fù)雜,是否存在多項(xiàng)式時(shí)間算法求解最優(yōu)t-松弛染色的問題有待進(jìn)一步研究。
【學(xué)位授予單位】：東南大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2017
【分類號(hào)】：O157.5

【參考文獻(xiàn)】

中國(guó)碩士學(xué)位論文全文數(shù)據(jù)庫(kù) 前1條

1 齊秀媛;圖的條件染色和非正常條件染色[D];山東師范大學(xué);2014年

，

本文編號(hào)：1284289