路的Hamiltonian色數(shù)的上界與偽貪婪算法.pdf

1、一個(gè)n階連通圖G的哈密頓染色c就是對(duì)這個(gè)連通圖所有頂點(diǎn)的一個(gè)顏色分配方案(每一個(gè)顏色用一個(gè)正整數(shù)來表不)，對(duì)于G中任意兩個(gè)互不相同的頂點(diǎn)u和u，滿足｜c(diǎn)(u)-c(u)｜+D(u,u)≥n-1，其中D(u，u)表不G中最長(zhǎng)的u-u路的長(zhǎng)度。Hc(c)表不在G的一個(gè)哈密頓染色c中分配給頂點(diǎn)的最大顏色值(正整數(shù))，圖G的哈密頓色數(shù)hc(G)是指最小的hc(c)(其中c取遍G的所有哈密頓染色)。對(duì)于n階路Pn，G.Chartrand,L.Ne

2、besky和P.zhang給出了結(jié)論：對(duì)于任意正整數(shù)n，有hc(Pn)=ac(Pn)≤(n-1/2)+1成立。并進(jìn)一步得出： 對(duì)于任意奇數(shù)n≥7，有hc(Pn)=ac(Pn)≤(n-1/2)-(n-1)/2+4，在本文中，我們提出一種路的哈密頓染色的偽貪婪算法，并得出結(jié)論：對(duì)所有偶正整數(shù)n≥10，hc(Pn)=ac(Pn)≤(n-1)/2-n/2-[10/n]+6。對(duì)于偶正整數(shù)n≥10，這個(gè)結(jié)論改進(jìn)了路Pn的哈密頓色數(shù)上界，并且