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

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

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

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

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

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

6、在染色C中與頂點υ關(guān)聯(lián)的染顏色i的邊的數(shù)目。如果染色C滿足對圖G中每個頂點υ∈V和每種顏色i∈{1，2，…，k}，都有ci(υ)≥f(υ)成立，則稱C為圖G的f-邊覆蓋染色.能對圖G進行，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類的。如果對所有的頂點υ，都有f(υ)=1，則有δf=δ，此時圖G的，f-邊覆蓋染色就退化為通一般意義上的邊覆蓋染色。能夠?qū)DG進行邊覆蓋染色所需的最大顏色數(shù)，稱為圖G的邊覆蓋色數(shù)，記為x'c(G).類似的，圖關(guān)于邊覆蓋染色也可以進行分類，即若x'c(G)=δ則稱G是C1類的，否則稱G是C2類的。對于正則圖來說，其關(guān)于邊覆蓋染

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

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

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

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