圖上幾類邊覆蓋染色問題的研究.pdf

1、圖論的研究已經(jīng)有二百多年的歷史，早在1736年Euler就用圖論方法解決了著名的哥尼斯堡七橋問題.隨著現(xiàn)代生產(chǎn)和科學(xué)技術(shù)的發(fā)展，圖論方法得到了廣泛的應(yīng)用，使圖論成為現(xiàn)代數(shù)學(xué)科學(xué)中的重要學(xué)科。由四色猜想誘導(dǎo)出來的圖的染色理論在圖論研究中占有重要的地位。目前，圖的染色理論已成為圖論中的一個(gè)重要分支，它在計(jì)算機(jī)理論、最優(yōu)化、網(wǎng)絡(luò)設(shè)計(jì)等方面都有著重要的應(yīng)用，例如在Hessians矩陣的計(jì)算、網(wǎng)絡(luò)中的數(shù)據(jù)傳輸?shù)确矫妗D的染色問題有很多，諸如邊染色

2、、點(diǎn)染色、面染色和全染色問題等，其中最基本的染色問題之一就是圖的邊染色。圖的正常邊染色就是把圖的邊集分解為一些互不相交的邊獨(dú)立集的并的方法。在圖的正常邊染色理論中有著名的Vizing定理，而其中圖關(guān)于正常邊染色的分類問題一直是研究的熱點(diǎn)之一。近年來，人們開始考慮把圖的邊集分解為其它形式，得到一些新的邊染色問題并進(jìn)行研究。本文主要討論了圖的邊覆蓋染色、f-邊覆蓋染色、分?jǐn)?shù)，f-邊覆蓋染色等。
　　 本研究用G(V(G)，E(G))

3、表示一個(gè)圖，其中V(G)是圖G的頂點(diǎn)集，E(G)是圖G的邊集.假設(shè)S是一個(gè)集合，用｜S｜表示集合S的基數(shù)。如果圖G中不允許出現(xiàn)重邊和環(huán)則稱G為簡(jiǎn)單圖，如果圖G中允許出現(xiàn)重邊但不允許出現(xiàn)環(huán)則稱G為多重圖，在本文中，如果沒有特別說明，我們所說的圖是指簡(jiǎn)單圖。對(duì)圖G中的點(diǎn)υ，用dG(υ)表示頂點(diǎn)υ的度，用NG(υ)表示υ的鄰點(diǎn)集.我們用δ(G)和△(G)分別表示圖G的最小度和最大度，即δ(G)=min{dG(υ)：υ∈V(G)}，△(G)=m

4、ax{dG(υ)：υ∈V(G)}.不致產(chǎn)生混淆時(shí)，我們用V，E，N(υ)，δ，△分別代替V(G)，E(G)，NG(υ)，δ(G)，△(G)。如果圖G滿足△(G)=δ(G)=d，則稱圖G是d-正則圖，3-正則圖通常被稱為立方圖。如果圖G的頂點(diǎn)集可以劃分為兩個(gè)互不相交的子集V1和V2，且G的任意一條邊關(guān)聯(lián)的兩個(gè)端點(diǎn)分別在V1和V2中，則稱圖G為二部圖。若圖G中存在一點(diǎn)u使得G-u是一個(gè)具有二劃分為(X，Y)的二部圖，則稱G為近似二部圖，記為

5、G(X，Y；u).如果G(V，E)是圖G1(V1，E1)和圖G2(V2，E2)的完全并(圖G1和圖G2沒有公共頂點(diǎn))，即V=V1∪V2并且E=E1∪E2∪{uυ：u∈V1，υ∈V2)，則稱圖G(V，E)是連結(jié)圖。假定對(duì)V(G)中每個(gè)頂點(diǎn)υ，都用一個(gè)正整數(shù)，f(υ)給以賦值，且要求1≤f(υ)≤d(υ)。我們用正整數(shù)1，2，…，k來表示顏色，如果C是邊集E(G)到集合{1，2，…，k)的映射，則稱C為圖G的k-邊染色.我們用ci(υ)表示

6、在染色C中與頂點(diǎn)υ關(guān)聯(lián)的染顏色i的邊的數(shù)目。如果染色C滿足對(duì)圖G中每個(gè)頂點(diǎn)υ∈V和每種顏色i∈{1，2，…，k}，都有ci(υ)≥f(υ)成立，則稱C為圖G的f-邊覆蓋染色.能對(duì)圖G進(jìn)行，f-邊覆蓋染色所使用的顏色的最大數(shù)目，稱為圖G的，f-邊覆蓋色數(shù)，記為x'fc(G)。令()其中()是指不大于d(υ)/f(υ)的最大整數(shù)。已知δf-1≤x'fc(G)≤δf.由上面的式子知，圖G的f-邊覆蓋色數(shù)x'fc(G)要么等于δf-1，要么等于

7、δf，由此我們根據(jù)x'fc(G)把圖分為兩大類：若x'fc(G)=δf則稱G是，fc-1類的，否則稱G是fc-2類的。如果對(duì)所有的頂點(diǎn)υ，都有f(υ)=1，則有δf=δ，此時(shí)圖G的，f-邊覆蓋染色就退化為通一般意義上的邊覆蓋染色。能夠?qū)DG進(jìn)行邊覆蓋染色所需的最大顏色數(shù)，稱為圖G的邊覆蓋色數(shù)，記為x'c(G).類似的，圖關(guān)于邊覆蓋染色也可以進(jìn)行分類，即若x'c(G)=δ則稱G是C1類的，否則稱G是C2類的。對(duì)于正則圖來說，其關(guān)于邊覆蓋染

8、色的分類問題等價(jià)于其關(guān)于正常邊染色的分類問題。因此，圖關(guān)于邊覆蓋染色的分類問題也是NP-完全的。對(duì)任意的圖討論它關(guān)于邊覆蓋染色的分類問題是非常困難的，但對(duì)一些特殊的圖類討論其分類問題是可能的。我們知道，在討論圖的分類問題時(shí)，“臨界”是一個(gè)非常重要的概念。如果圖G是連通的非完全圖且滿足x'fc(G)=δf-1，且對(duì)任意的u，υ∈V，e=uυ()E都有x'fc(G+e)=δf成立，則稱圖G是，f-邊覆蓋臨界的。如果對(duì)所有的頂點(diǎn)υ取，f(υ)

9、=1，則相應(yīng)的有邊覆蓋臨界圖的概念。研究，f-邊覆蓋臨界圖的性質(zhì)對(duì)于解決圖的關(guān)于，f-邊覆蓋染色的分類問題具有重要意義。分?jǐn)?shù)圖論是圖論的一個(gè)重要分支。圖的分?jǐn)?shù)邊染色和分?jǐn)?shù)邊覆蓋染色都是一些相對(duì)較新的研究方向，他們分別對(duì)討論圖的正常邊染色和邊覆蓋染色有十分重要的作用。在本文中我們首次提出了圖的分?jǐn)?shù)f-邊覆蓋染色的概念，它對(duì)討論圖的f-邊覆蓋染色問題同樣也有重要的作用。因此，討論圖的分?jǐn)?shù)，f-邊覆蓋染色也是非常有意義的。圖G的分?jǐn)?shù)f-邊覆蓋

10、染色是指給G的每一個(gè)f-邊覆蓋F分配非負(fù)權(quán)ωF，使得對(duì)任意的e∈E(G)滿足∑F()eωF≤1，其中∑F()e是對(duì)含邊e的G的所有的，f-邊覆蓋求和。圖G的分?jǐn)?shù)f-邊覆蓋色數(shù)x'fcf(G)是指可以對(duì)圖G進(jìn)行分?jǐn)?shù)f-邊覆蓋染色，且使∑FωF取最大值，其中求和是對(duì)G的所有的f-邊覆蓋F進(jìn)行。圖的邊覆蓋染色問題與圖的正常邊染色問題有很多對(duì)應(yīng)的結(jié)論，但其本質(zhì)上有很大的不同，邊覆蓋染色的大多數(shù)結(jié)論無法從正常邊染色的結(jié)論中直接推出來。對(duì)這兩類問題

11、進(jìn)行研究的思路和方法是完全不同的，邊覆蓋染色研究的難度是非常大的。
　　 本文主要考慮圖的幾類染色問題。我們主要討論圖的邊覆蓋染色、f-邊覆蓋染色、分?jǐn)?shù)f-邊覆蓋染色等。本文分四章進(jìn)行討論。第一章，我們首先介紹一些用到的基本概念和定義。然后給出有關(guān)的染色的定義和研究歷史并給出了本文的主要結(jié)果。第二章，我們討論了邊覆蓋染色的分類。首先給出了一般圖是C1類圖或C2類圖的一些充分條件，給出了一種構(gòu)造邊覆蓋臨界圖的方法，然后對(duì)某些特殊圖