若干新的s-偶圖的Ramsey數(shù)

楊 洪, 吳 璞, 鄧 飛

(1. 成都大學(xué) 信息科學(xué)與工程學(xué)院， 四川 成都 610106; 2. 廣州大學(xué) 計(jì)算科技研究院， 廣東 廣州 510006; 3. 成都理工大學(xué) 信息科學(xué)與技術(shù)學(xué)院， 四川 成都 610059)

本文只考慮沒有重邊或環(huán)的圖.對(duì)于圖G=(V,E)，用V(G)和E(G)分別表示圖G的頂點(diǎn)集和邊集.一個(gè)分類數(shù)為m和n的完全偶圖可以用Km,n來表示.更多圖論的概念和符號(hào)請(qǐng)參考文獻(xiàn)[1].Erd?s等[2]在1978年開始了邊Ramsey數(shù)的研究，后來Faudree等[3]、Lortz等[4]和Pikhurko等[5-6]繼續(xù)這一研究工作.

對(duì)于正整數(shù)s，以及兩個(gè)偶圖G和H，s-偶圖Ramsey數(shù)BRs(G,H)是一個(gè)最小正整數(shù)t，使得每一個(gè)Ks,t的2-邊著色都含有1色的圖G或者含有2色的圖H.

文獻(xiàn)[7-9]提出了s-偶圖Ramsey數(shù)的概念,文獻(xiàn)[9]得到了關(guān)于K2,3和K3,3的s-偶圖Ramsey數(shù)對(duì)于s≤7的一些精確值.最近，Wan等[10]應(yīng)用一些計(jì)算技術(shù)，確定出了K2,3和K3,3的2色s-偶圖Ramsey數(shù)對(duì)于s≥8的一些精確值.致力于圖論算法研究的基礎(chǔ)上[11-12]，本文提出了一個(gè)新的整數(shù)線性規(guī)劃模型，對(duì)其他類型的完全偶圖，計(jì)算出了雙色s-偶圖Ramsey數(shù)的精確值.實(shí)驗(yàn)結(jié)果表明，該模型比文獻(xiàn)[10]提出的模型更加高效.利用該模型，成功地確定了許多個(gè)新的s-偶圖Ramsey數(shù)的精確值.

1 計(jì)算技術(shù)

對(duì)于完全偶圖Ks,t，Ks1,t1和Ks2,t2，建立一個(gè)新的線性規(guī)劃模型，以確定是否存在一個(gè)Ks,t的2-邊著色方案，使得在該方案中既不含1色的Ks1,t1，也不含2色的Ks2,t2.

1.1 以前的工作

文獻(xiàn)[10]提出了一種計(jì)算雙色s-偶圖Ramsey數(shù)的整數(shù)線性規(guī)劃(ILP)方法.為了保持論文的獨(dú)立性，將模型重述如下.

設(shè)Ks,t的頂點(diǎn)集是A∪B，其中A={a1,a2,…,as}，B={b1,b2,…,bt}，且A和B都是獨(dú)立集.對(duì)每一條邊{u,v}(u∈A,v∈B)，引入布爾變量xu,v,c(1≤c≤2)，且xu,v,c=1當(dāng)且僅當(dāng){u,v}著色c.于是，對(duì)任意uv∈E(Ks,t)，有

xu,v,1+xu,v,2=1

(1)

對(duì)每個(gè)Ks,t中的K2,3，不妨設(shè)頂點(diǎn)分別為a1,a2,b1,b2,b3，有

xa1,b1,1+xa1,b2,1+xa1,b3,1+xa2,b1,1+xa2,b2,1+xa2,b3,1≤5

(2)

對(duì)每個(gè)Ks,t中的K3,3，不妨設(shè)頂點(diǎn)分別為a1,a2,a3,b1,b2,b3，有

(3)

對(duì)于給定的正整數(shù)s和t，如果不存在滿足約束條件(1)(2)(3)的解，那么就有BRs(K2,3,K3,3)≤t；否則就有BRs(K2,3,K3,3)≥t+1.利用上述的整數(shù)線性規(guī)劃模型，成功地求出了BRs(K2,3,K3,3)的所有情形.

1.2 新線性規(guī)劃模型

對(duì)于某些階數(shù)較大的偶圖，1.1小節(jié)中的整數(shù)線性規(guī)劃(ILP)模型未必能在合理的時(shí)間內(nèi)求解.下面，對(duì)較大的圖，引入一個(gè)新的ILP模型來計(jì)算雙色s-偶圖Ramsey數(shù)的精確值，描述如下.

假設(shè)完全偶圖Ks,t的頂點(diǎn)集是A∪B，其中A={a1,a2,…,as}.設(shè)G是Ks,t的一個(gè)子圖，u,v是正整數(shù)，且

Z2={0,1}，

y=(y1,y2,…,ys)∈Z2×Z2×…×Z2，

Xy(G)={v|v∈B,v∈NG(ai)對(duì)任意yi=1，且v?NG(ai)對(duì)任意yi=0}，

定理設(shè)Ks,t是一個(gè)完全偶圖，對(duì)于整數(shù)s1,t1,s2及t2，存在一個(gè)Ks,t的2-邊著色方案使得在該方案中既不含1色的Ks1,t1也不含2色的Ks2,t2，當(dāng)且僅當(dāng)存在一個(gè)Ks,t的子圖G滿足Ds1,t1(G)=?及Ms2,t2(G)=?.

證明設(shè)完全偶圖Ks,t的頂點(diǎn)集是A∪B，其中A={a1,a2,…,as}.現(xiàn)在假設(shè)存在一個(gè)Ks,t的2-邊著色方案使得方案中既不含1色的Ks1,t1也不含2色的Ks2,t2.將Ks,t中的1色導(dǎo)出的子圖記為G.先考慮以下兩種情形：

情形1：Ds1,t1(G)≠?.

情形2：Ms1,t1(G)≠?.

如果存在滿足Ds1,t1(G)=?，Ms1,t1(G)=? 的Ks2,t2的子圖G，那么就將G中的所有邊著顏色1，其余邊都著顏色2.現(xiàn)考慮如下兩種情形：

現(xiàn)將條件Ds1,t1(G)=?，Ms1,t1(G)=?應(yīng)用到如下約束中：

因此，提出一個(gè)新的ILP模型，其約束條件如下所示：

(4)

(5)

(6)

于是可得，存在滿足Ds1,t1(G)=?，Ms1,t1(G)=? 的Ks,t的子圖G，當(dāng)且僅當(dāng)存在一個(gè)滿足約束條件(4)(5)(6)的解.由定理可知，存在一個(gè)Ks,t的2-邊著色方案滿足既不含有1色的圖Ks1,t1也不含有2色的圖Ks2,t2，當(dāng)且僅當(dāng)存在一個(gè)滿足約束條件(4)(5)(6)的解.

2 計(jì)算結(jié)果

如表1所示，文獻(xiàn)[9]和文獻(xiàn)[10]確定了BRs(K2,3,K3,3)的值.但是，欲求BRs(K3,3,K3,3)的值或其他偶圖Ramsey數(shù)的值，用文獻(xiàn)[10]提供的ILP模型仍然很難確定.

表1 BRs(K2,3,K3,3)的精確值Table 1 Exact values of BRs(K2,3,K3,3)

為了驗(yàn)證新ILP模型的有效性，在2.66 GHz的CPU環(huán)境下利用軟件Gurobi[8]，分別用兩種ILP模型求解BRs(K2,3,K3,3)的值，通過實(shí)例將這兩個(gè)模型進(jìn)行比較.設(shè)文獻(xiàn)[10]中原有的ILP模型和本文中的新ILP模型分別用old ILP和new ILP來表示.實(shí)驗(yàn)結(jié)果表明，對(duì)任意的s∈{5,6,…,10}，都無法在1 h內(nèi)通過old ILP模型求出相應(yīng)的精確值.可是，當(dāng)s=5,6時(shí)，在0.01 s內(nèi)通過new ILP模型成功地求出了相應(yīng)的精確值.當(dāng)s=19，t=23時(shí)，僅用5.35 s就通過new ILP模型成功地求出了相應(yīng)的精確值.而且，通過new ILP模型成功地求出了55個(gè)新的精確值，結(jié)果如表2～表11所示.

表2 BRs(K3,3,K3,3)的精確值Table 2 Exact values of BRs(K3,3,K3,3)

表3 BRs(K2,4,K3,3)的精確值Table 3 Exact values of BRs(K2,4,K3,3)

表4 BRs(K2,5,K3,3)的精確值Table 4 Exact values of BRs(K2,5,K3,3)

表5 BRs(K2,6,K3,3)的精確值Table 5 Exact values of BRs(K2,6,K3,3)

表6 BRs(K2,7,K3,3)的精確值Table 6 Exact values of BRs(K2,7,K3,3)

表7 BRs(K3,4,K3,3)的精確值Table 7 Exact values of BRs(K3,4,K3,3)

表8 BRs(K3,5,K3,3)的精確值Table 8 Exact values of BRs(K3,5,K3,3)

表9 BRs(K2,3,K3,4)的精確值Table 9 Exact values of BRs(K2,3,K3,4)

表10 BRs(K2,4,K3,4)的精確值Table 10 Exact values of BRs(K2,4,K3,4)

表11 BRs(K2,5,K3,4)的精確值Table 11 Exact values of BRs(K2,5,K3,4)

3 結(jié)束語

在文獻(xiàn)[9]中，Bi等首先開始研究了當(dāng)s≤7時(shí)K2,3和K3,3的s-偶圖Ramsey數(shù)的情況.文獻(xiàn)[10]提出一些計(jì)算技術(shù)來獲得了K2,3和K3,3的s-偶圖Ramsey數(shù)的其他所有情形.然而，利用文獻(xiàn)[10]中的方法，無法在1 h以內(nèi)求出當(dāng)s≥5時(shí)的BRs(K3,3,K3,3).本文提出了一個(gè)新的ILP模型，能求出當(dāng)5≤s≤10時(shí)的BRs(K3,3,K3,3)的精確值.而且，對(duì)其它多種組合下的完全偶圖情形，通過新ILP模型求出了多達(dá)55個(gè)2色s-偶圖Ramsey數(shù)的精確值.