圖的邊覆蓋染色及分?jǐn)?shù)邊染色.pdf

1、圖的染色理論是圖論中的一個(gè)重要分支．圖的染色種類有很多，諸如邊染色、點(diǎn)染色、面染色和全染色等．其中研究最多，結(jié)果也較完善的就是圖的邊染色．圖的正常的邊染色就是把圖的邊集分解為一些互不相交的邊的獨(dú)立集的并的方法．在圖的正常邊染色理論中有著名的Vizing定理，而其中關(guān)于正常邊染色的圖的分類問題一直是研究的熱點(diǎn)．近年來，人們開始考慮把圖的邊集分解為其它形式，得到一些推廣的邊染色并進(jìn)行研究．本文主要是討論了圖的邊覆蓋染色、f-邊覆蓋染色、分?jǐn)?shù)

2、邊覆蓋染色和分?jǐn)?shù)邊染色等． 我們用Ｇ(Ｖ,Ｅ)表示一個(gè)圖，其中Ｖ是頂點(diǎn)集，Ｅ是邊集．設(shè)S是一個(gè)集合，｜S｜表示集合S的基數(shù)．在本文中我們所說的圖通常指有限簡(jiǎn)單圖．如果圖G中允許有重邊則稱G為重圖．對(duì)圖G中的點(diǎn)υ，用d<,G>(υ)表示頂點(diǎn)υ的度，用N<,G>(υ)表示υ的鄰點(diǎn)集δ(G)＝min{d<,G>(υ)：υ∈Ｖ(G)}，Δ(G)＝maX{d<,G>(υ)：υ∈Ｖ(G)｝，則δ(G)和Δ(G)分別表示圖G的最小度和最大度．

3、在不產(chǎn)生混淆的情況下，我們常用Ｖ，Ｅ，Ｎ(υ)，δ，Δ分別代替Ｖ(G)，E(G)，N<,G>(υ)，δ(G)，Δ(G)． 令G<,δ>表示圖G中由最小度點(diǎn)導(dǎo)出的子圖．如果Δ(G)＝δ(G)＝d則稱G是d-正則圖，通常也稱3-正則圖為立方圖．如果圖G的頂點(diǎn)集可以劃分為兩個(gè)互不相交的子集Ｖ<,1>和Ｖ<,2>且G的任何一條邊的兩個(gè)端點(diǎn)分別在Ｖ<,1>和Ｖ<,2>中，則稱圖G為二部圖．若圖G中存在一點(diǎn)u使得G—u是一個(gè)具有二劃分為(Ｘ

4、，Ｙ)的二部圖則稱G為近似二部圖，記為G(Ｘ，Ｙ；u)．一個(gè)圈是指圖中每個(gè)點(diǎn)的度都是2的連通圖，稱含有奇數(shù)條邊的圈為奇圈，含有偶數(shù)條邊的圈為偶圈． 我們用正整數(shù)1，2，…來表示顏色，若Ｃ是邊集E到集合{1，2，…，к}的映射，即Ｃ：Ｅ→{1，2，…，к}，則稱Ｃ為圖G的к-邊染色．令G<,i>(υ)表示在圖G的在染色C中與頂點(diǎn)υ關(guān)聯(lián)的染i色邊的數(shù)目．假定對(duì)Ｖ中每個(gè)頂點(diǎn)υ都已賦以正整數(shù)f(υ)且要求1≤f(υ)≤d(υ)．若染色

5、C使圖G中任意頂點(diǎn)υ∈Ｖ和i∈{1，2，…，к}，都有C<,i>(υ)≥f(υ)成立，則稱C為圖G的f-邊覆蓋（上面有化學(xué)方程式）由上面的式子知，圖G的f-邊覆蓋色數(shù)x＇<,fc>(G)要么等于δ<,f>-1，要么等于δ<,f>，由此我們根據(jù)x＇<,fc>(G)把圖分為兩大類：若x＇<,fc>(G)=δ<,f>則稱G是c<,f>I類的，否則稱G是c<,f>ll類的．若對(duì)所有的頂點(diǎn)υ，都滿足f(υ)=1，此時(shí)δ<,f>=δ，則圖G的f-

6、邊覆蓋染色就是通常討論的一般的邊覆蓋染色．對(duì)圖G進(jìn)行邊覆蓋染色所需的最大顏色數(shù)(求最小沒有意義)稱為圖G的邊覆蓋色數(shù)，記為x＇<,c>(G)．類似的，對(duì)于邊覆蓋染色同樣也有分類問題，即若x＇<,c>(G)=δ則稱G是CI類的，否則稱G是Cll類的．對(duì)于正則圖而言，其邊覆蓋染色的分類問題等價(jià)于正常的邊染色分類問題．因此，邊覆蓋染色的分類問題也是ⅣP-完全的．對(duì)任意的圖討論它的邊覆蓋染色分類是很困難的，但對(duì)一些特殊圖討論其分類是可能的．討論

7、圖的分類問題時(shí)，“臨界”的概念是很重要的．設(shè)G是連通的非完全圖且x＇<,fc>(G)=δ<,f>-1，如果對(duì)任意的u，υ∈V，e=uυ E都有x＇<,fc>(G+e)=δf成立，則稱G是f-邊覆蓋臨界的．同樣，若對(duì)所有的頂點(diǎn)υ取。f(υ)=1，則有邊覆蓋臨界圖的概念．而研究f-邊覆蓋臨界圖(或邊覆蓋臨界圖)的性質(zhì)與構(gòu)造對(duì)于解決圖的基于f-邊覆蓋染色(或邊覆蓋染色)的分類問題具有重要意義． 另一方面，分?jǐn)?shù)邊覆蓋染色和分?jǐn)?shù)邊染色也是近幾年出

8、現(xiàn)的新的研究方向．而且，分?jǐn)?shù)邊覆蓋色數(shù)和分?jǐn)?shù)邊色數(shù)分別對(duì)討論圖的邊覆蓋染色分類和正常邊染色分類有重要的作用．因此，討論圖的分?jǐn)?shù)邊覆蓋染色和分?jǐn)?shù)邊染色也是非常有意義的． 圖G的分?jǐn)?shù)邊覆蓋染色是指給G的每一個(gè)邊覆蓋C分配非負(fù)權(quán)ωc，使得對(duì)任意的e∈E(G)滿足∑c ωc≤1(其中∑c e是對(duì)含邊e的G的所有的邊覆蓋求和)，相應(yīng)的分?jǐn)?shù)邊覆蓋色數(shù)x<,c><'f>(G)是指可進(jìn)行分?jǐn)?shù)邊覆蓋染色的∑cωc(是對(duì)G的所有的邊覆蓋c求和)的

9、最大值． 類似地，圖G的分?jǐn)?shù)邊染色是指給G的每一個(gè)邊匹配M分配非負(fù)權(quán)ωM，使得對(duì)任意的e∈E(G)滿足∑M eωM≥1(其中∑M e。是對(duì)含邊e的G的所有的匹配求和)，相應(yīng)的分?jǐn)?shù)邊色數(shù)x'<,f>(G)是指可進(jìn)行分?jǐn)?shù)邊染色的∑<,M>ωM(是對(duì)G的所有的匹配M求和)的最小值。 關(guān)于圖的邊覆蓋染色的結(jié)論與圖的正常邊染色的結(jié)論有很多是類似，但是其本質(zhì)上有很大的不同，很多結(jié)論無法從正常邊染色的結(jié)論中推出來．對(duì)二者進(jìn)行研究

10、所用的方法和手段也有很大的不同，其研究是相對(duì)獨(dú)立的。 本文分為五章.第一章介紹了圖論的基本概念和邊染色的歷史和發(fā)展?fàn)顩r，給出了一個(gè)簡(jiǎn)短但相對(duì)完整的綜述．第二章討論了邊覆蓋染色的分類，首先是給出一般圖是CI或CII類圖的一些充分條件，然后又對(duì)某些特殊圖的分類進(jìn)行了討論得到一些有意義的結(jié)果，最后對(duì)邊覆蓋臨界圖的性質(zhì)和構(gòu)造進(jìn)行了討論，給出了一種構(gòu)造邊覆蓋臨界圖的構(gòu)造方法。第三章我們首次對(duì)f-邊覆蓋染色的分類和f-邊覆蓋臨界圖的性質(zhì)