孔靜

(泰山學(xué)院數(shù)學(xué)與系統(tǒng)科學(xué)學(xué)院，山東泰安 271021)

這樣我們就可以將染色問題轉(zhuǎn)化成下面的整數(shù)規(guī)劃問題(Ⅰ):

1 引言

自從18世紀(jì)Euler開始對圖論進(jìn)行研究，圖論吸引了越來越多學(xué)者的目光，并且已經(jīng)成為了一個十分重要的研究領(lǐng)域.圖的染色問題是圖論中一個非常重要的問題，在實際生活中有著廣泛的應(yīng)用.染色問題中一個非常著名的問題就是四色定理，在其被探討的百年期間大大推動了圖論的發(fā)展.

一個圖G的k正常著色，是指將G的頂點(diǎn)分配k中顏色，使得染同一種顏色的任意兩個頂點(diǎn)在圖G中沒有邊相連，即等價于染同一種顏色的頂點(diǎn)構(gòu)成了圖G的一個獨(dú)立點(diǎn)集.一個圖G的正常著色所需的最小的k的值稱為圖G的色數(shù)，記為χ(G)=k.在人們對圖的染色問題用各種方法進(jìn)行研究的同時，也引申出了與圖的染色問題密切相關(guān)的一些新的領(lǐng)域，如圖的分?jǐn)?shù)染色.對圖的分?jǐn)?shù)染色的研究最早可追溯到對圖的多重染色的研究.E.Scheinerma，D.Ullman在文［1］對分?jǐn)?shù)染色的問題進(jìn)行了系統(tǒng)的闡述.在該書中，作者首先給出了對圖的理論進(jìn)行分?jǐn)?shù)推廣的方法，特別對于染色問題，引出了分?jǐn)?shù)染色的概念，它是對圖的染色問題的一個推廣.

我們可以將染色問題轉(zhuǎn)化為一個線性規(guī)劃問題.因為染同一種顏色的點(diǎn)在圖G中構(gòu)成了圖G的獨(dú)立點(diǎn)集，而圖的一個染色就將G的頂點(diǎn)集分割成由獨(dú)立點(diǎn)集構(gòu)成的集合.因此我們可以將求一個圖的色數(shù)問題轉(zhuǎn)化成尋找G的若干獨(dú)立集，使得這些獨(dú)立集的個數(shù)最少，并且滿足:G的任意頂點(diǎn)x都至少包含在一個獨(dú)立集中.我們將所有頂點(diǎn)和所有獨(dú)立集分別進(jìn)行標(biāo)號，V(G)={v1，v2，…，vn}，I(G)={I1，I2，…，Im}可以得到一個0－1矩陣M=(mij)n×m(稱為頂點(diǎn)—獨(dú)立集關(guān)系的描述矩陣)，其中

這樣我們就可以將染色問題轉(zhuǎn)化成下面的整數(shù)規(guī)劃問題(Ⅰ):

這里My≥1中的1是全1的m維列向量.

我們將上面規(guī)劃的約束放寬，由要求y∈{0，1}，變?yōu)橐髖≥0，這樣得到一個線性規(guī)化問題(Ⅱ):

已知任意一個圖的染色問題，即整數(shù)規(guī)劃問題(Ⅰ)是一個NP－complete問題.而上面的線性規(guī)劃問題(Ⅱ)有多項式時間的算法.設(shè)整數(shù)規(guī)劃問題(Ⅰ)的最優(yōu)解為y*，線性規(guī)化問題(Ⅱ)的最優(yōu)解為y＊＊，顯然y＊＊≤y*.這樣我們可以用y＊＊對y*進(jìn)行估計.因為線性規(guī)劃問題(Ⅱ)的解是一個有理數(shù)，所以對任意給定一個圖G，我們定義為分?jǐn)?shù)色數(shù)，記為χf(G).

目前人們對分?jǐn)?shù)染色的研究一般集中在兩個方面，一是研究一些特殊圖的分?jǐn)?shù)色數(shù)，如Kneser圖，循環(huán)圖等及一些圖的運(yùn)算下的分?jǐn)?shù)色數(shù)［1－4］.如對圖的乘積，已經(jīng)證明了對于任意的兩個圖G1和G2，G1和G2的分隔乘積(記為G1*G2)，G1和G2的字典序乘積(記為G1［G2］)都滿足:χf(G1*G2)= χf(G1)χf(G2)≤χ(G1)χ(G2)，χf(G1［G2］)=χf(G1)χf(G2)［1］.另一方面研究一些有關(guān)圖的染色的猜想是否關(guān)于圖的分?jǐn)?shù)著色依然成立，如Ed¨os－Faber－Lovásze猜想，Hadwiger猜想等等［1］.因此，此領(lǐng)域還有大量的未解決的問題有待研究.

在本文中我們對兩個圖的強(qiáng)乘積的分?jǐn)?shù)色數(shù)進(jìn)行了研究.任意給定兩個圖G和H，我們證明了ω(G)ω(H)≤χf(GH)≤χ(G)χ(H)，這樣就可以通過圖G和H本身的性質(zhì)來對它們的強(qiáng)乘積的分?jǐn)?shù)色數(shù)進(jìn)行估計.

2 基本概念

對于無向圖G=(V，E)，我們分別用V(G)和E(G)表示圖G的頂點(diǎn)集合和邊集合.設(shè)頂點(diǎn){u，v}?V(G)，我們用無序頂點(diǎn)對uv來標(biāo)記圖中的一條邊，記u，v是這條邊的頂點(diǎn)，并且稱u，v與該邊相關(guān)聯(lián)，反之亦然.與同一條邊相關(guān)聯(lián)的兩個頂點(diǎn)稱為是相鄰的，與同一個頂點(diǎn)相關(guān)聯(lián)的兩條邊也稱為是相鄰的.頂點(diǎn)重合為一點(diǎn)的邊稱為環(huán).如果一個圖的頂點(diǎn)集和邊集都是有限集，我們稱之為有限圖.在本文中我們考慮的都是沒有重邊和環(huán)的有限的無向圖.

每一對頂點(diǎn)都有一條邊相連的圖稱為完全圖.V(G)中一個子集稱為一個團(tuán)，如果該子集中任意兩個點(diǎn)在G中都相鄰.而如果S?V(G)中任意兩點(diǎn)在G中都不相鄰，則稱S為G的一個獨(dú)立集.設(shè)C是G的任意一個獨(dú)立集，如果C不包含在G的其他獨(dú)立集中，那么我們稱C是一個極大獨(dú)立集.我們用IG表示G的所有極大獨(dú)立集的集合;用I(G)表示G的所有獨(dú)立集集合.G中包含頂點(diǎn)最多的團(tuán)稱為最大團(tuán)，其所包含頂點(diǎn)的個數(shù)稱為G的團(tuán)數(shù)，我們用ω(G)表示.G的所有團(tuán)的集合我們用C(G)表示.

設(shè)頂點(diǎn)集V1?V(G)，V2?V(G)，則V1×V2={(v1，v2)∶v1∈V1，v2∈V2}.下面我們定義兩個圖G和H的幾種乘積形式.G和H的強(qiáng)乘積，用GH表示，它是這樣一個圖，其頂點(diǎn)集是{(u，v)∶u∈V(G)，v∈V(H)}=V(G)×V(H);兩個頂點(diǎn)(u，x)(v，y)如果滿足下面三個條件中其中一條:

(1)uv∈E(G)，xy∈E(H);

(2)uv∈E(G)，x=y;

(3)u=v，xy∈E(H).

兩個圖G和H的分隔乘積，記為G*H，頂點(diǎn)集是V(G)×V(H);兩個頂點(diǎn)(u，x)(v，y)∈E(G*H)當(dāng)且僅當(dāng)uv∈E(G)或者xy∈E(H).

其他的有關(guān)圖論的定義和符號請參見文獻(xiàn)［5］.

3 主要結(jié)果

我們將對強(qiáng)乘積圖的分?jǐn)?shù)色數(shù)進(jìn)行討論，證明下面的定理.

定理1任意給定兩個圖G和H，ω(G)ω(H)≤χf(GH)≤χ(G)χ(H).

我們首先證明兩個引理.

引理1 設(shè)I，J分別為圖G和H的極大獨(dú)立集，則I×J一定為GH的一個極大獨(dú)立集.

引理2 設(shè)C，Q分別為圖G和H的最大團(tuán)，則C×Q一定為GH的一個最大團(tuán)，即ω(GH)= ω(G)ω(H).

證明:因為C，Q分別為圖G和H的團(tuán)，因此根據(jù)強(qiáng)乘積的定義，C×Q中的每一個頂點(diǎn)在GH中都是相鄰的，因此C×Q一定為GH的一個團(tuán).C×Q的頂點(diǎn)個數(shù)為|C|×|Q|，由C，Q分別為圖G和H的最大團(tuán)知，C×Q的頂點(diǎn)個數(shù)在GH的所有團(tuán)中也是最大的.因此C×Q一定為GH的一個最大團(tuán).

分隔乘積也是圖乘積的一種.對于兩個圖G和H的分隔乘積G*H，我們已知下面的結(jié)論成立.

引理3［1］任意給定兩個圖G和H，則I，J分別為圖G和H的極大獨(dú)立集等價于I×J為G*H的一個極大獨(dú)立集.

引理4［1］對于圖G和H，χf(G*H)=χf(G)χf(H)≤χ(G)χ(H).

下面我們給出定理1的證明.

證明:對于圖G和H，我們求χf(GH)就是求解線性規(guī)劃(Ⅱ'):

設(shè)求χf(G*H)對應(yīng)的線性規(guī)劃(Ⅳ)為:

其中B是G*H的頂點(diǎn)——極大獨(dú)立集關(guān)系的0－1描述矩陣.由引理1和引理3知，{I×J∶I∈IG，J∈IH}=IG*H?IGH，從而矩陣B是由A的若干列向量構(gòu)成的子矩陣，這意味著線性規(guī)劃(Ⅳ)的一個可行解一定為線性規(guī)劃(Ⅲ)的可行解，因此χf(G?H)≤χf(G*H).又根據(jù)引理4，

故

另一方面，線性規(guī)劃(Ⅲ)的對偶規(guī)劃為(DⅢ):其對應(yīng)的整數(shù)規(guī)劃為(IDⅢ)

由矩陣A的定義知，(IDⅢ)是從G?H的頂點(diǎn)集中挑選部分頂點(diǎn)，使這些頂點(diǎn)不在同一個獨(dú)立集中，也就是說在同一個團(tuán)中.因此(IDⅢ)的最優(yōu)值是圖G?H的最大團(tuán)所含頂點(diǎn)的個數(shù)，即最大團(tuán)數(shù)ω(G?H)，因此(DⅢ)的最優(yōu)值是分?jǐn)?shù)最大團(tuán)數(shù)，我們用ωf(G?H)表示，顯然ωf(G?H)≥ω(G?H).又由線性規(guī)劃的對偶性質(zhì)知，ωf(G?H)=χf(G?H).由引理2可得

綜合(1)和(2)即得:

［1］E.Scheinerma，D.Ullman.Fractional graph theory，a rational approach to graph theory［M］.New York:J.Wiley and Sons，1997.

［2］孫磊.Kneser圖的分?jǐn)?shù)染色的臨界性［J］.物理學(xué)學(xué)報，2002，22(A)2:238－243.

［3］G.J.Chang，L.Huang，X.Zhu.The circular chromatic numbers and the fractional chromatic number of distance graphs［J］.European Journal of Combinatorics，1998，19:423－431.

［4］D.C.Fish.Fractional colorings with large denominators［J］.Journal of Graph Theory，1995，20:403－409.

［5］J.A.Bondy，U.S.R.Murty.Graph theory with applications［M］.New York:Elsevier Science Publishing Co.，Inc，1976.