一類極大平面圖4-著色布爾方程組

賈永旺, 白蓮花, 烏力吉

(內(nèi)蒙古工業(yè)大學(xué)理學(xué)院 內(nèi)蒙古呼和浩特010051)

一類極大平面圖4-著色布爾方程組

賈永旺, 白蓮花, 烏力吉

(內(nèi)蒙古工業(yè)大學(xué)理學(xué)院 內(nèi)蒙古呼和浩特010051)

對(duì)極大平面圖的4-著色布爾方程組進(jìn)行研究,得到了該布爾方程組的5條性質(zhì),并且給出了求極大平面圖4-著色全部解的一個(gè)算法.

平面圖;極大平面圖;4-著色;布爾方程組

0 引言

圖的著色問(wèn)題具有重要意義,是圖論的主要研究?jī)?nèi)容之一.圖的著色問(wèn)題的研究起源于著名的4色猜想,即,每張地圖是否可以用4種顏色對(duì)國(guó)家進(jìn)行著色,使得相鄰的國(guó)家著不同的顏色.1977年文獻(xiàn)[1]通過(guò)計(jì)算機(jī)得到4色猜想證明,然而這一證明并沒(méi)有給出具體4-著色方法.目前,介紹求極大平面圖4-著色全部解的報(bào)道還很少見(jiàn),對(duì)于給定平面圖應(yīng)該怎樣去著色,仍然沒(méi)有一種行之有效的辦法.文獻(xiàn)[2-4]將極大平面圖的4色問(wèn)題轉(zhuǎn)化為簡(jiǎn)單布爾方程組的求解問(wèn)題,為研究4色問(wèn)題開(kāi)辟了一條新的途徑,文獻(xiàn)[5-9]對(duì)此問(wèn)題也作了研究.

我們對(duì)這類方程組進(jìn)行了探討,得到了它的5條重要性質(zhì),為求解該類問(wèn)題打下了理論基礎(chǔ).最后給出了求極大平面圖4-著色解的一個(gè)算法,該算法與以往的帶有窮舉性質(zhì)的算法不同,它不需要試探步,得到的都是正常4-著色解,從而提高了效率,同時(shí)它求出來(lái)的還是全部解.在本文中,凡不加以說(shuō)明的名詞術(shù)語(yǔ)和符號(hào),均采用文獻(xiàn)[3]中的規(guī)定.

1 基本概念

定義1[2]在一個(gè)圈中添加一個(gè)新的頂點(diǎn),并將新頂點(diǎn)與圈上所有頂點(diǎn)以邊連接后所得的圖稱為輪圖.新邊稱為輪圖的輻,記為Wn.

在Wn中可對(duì)應(yīng)n個(gè)不同的同構(gòu)于K4-e的子圖,在每個(gè)子圖上定義一個(gè)布爾變量xi(1≤i≤n),用其表示K4-e中對(duì)應(yīng)的二度頂點(diǎn)著色時(shí)顏色的異同(1表異色,0表同色,下同).設(shè)G是極大平面圖,設(shè)∏1,∏2,…,∏n是G的同構(gòu)于K4-e的子圖全體集,對(duì)每個(gè)∏i,如前定義一個(gè)變量xi,G的正常4-著色全體集C與n維布爾向量空間Vn的一個(gè)子集一一對(duì)應(yīng),在n維布爾向量空間或1,i=1,2,…,n}上定義了一個(gè)布爾函數(shù)

我們已有求Fn(x1,x2,…,xn)的遞推公式,其中,表示xi的逆元(下同):

設(shè)G的內(nèi)部頂點(diǎn)全體之集為{v1,v2,…,vk},對(duì)每個(gè)vi(i=1,2,…,k),得到一個(gè)輪圖Wi=G[vi∪N(vi)],這里N(vi)={u|viu∈E(G)}.由Wi又可以定義一個(gè)布爾函數(shù)Fi,這樣,就得到了布爾方程組我們稱其為G的4-著色布爾方程組,其中,上標(biāo)表示方程的編號(hào),下標(biāo)表示方程中含有變量的個(gè)數(shù).

引理1[2]任一極大平面圖G可4-著色問(wèn)題當(dāng)且僅當(dāng)布爾方程組(3)有解,進(jìn)一步地,(3)的每個(gè)解向量都對(duì)應(yīng)著G的一個(gè)正常4-著色,反之亦然.

2 主要結(jié)果

設(shè)G是極大平面圖,其頂點(diǎn)集為{v1,v2,…,vn},對(duì)其4-著色布爾方程組進(jìn)行了研究,得到了它的5條性質(zhì),并且給出了極大平面圖4-著色全部解的算法.

定義2把有n個(gè)布爾變量x1,x2,…,xn排成的序列看成是首尾相連的環(huán)狀序列,則由其中xk(1≤k≤n)處斷開(kāi),得到新的序列xk+1,xk+2,…,x1,x2,…,xk的過(guò)程,稱為序列關(guān)于xk的一個(gè)輪換,新序列記為xk+1,…,xn,…,xk.本文中,當(dāng)不會(huì)發(fā)生混淆時(shí),將采用該記號(hào).

2.1 布爾方程組的性質(zhì)

定理1對(duì)序列x1,x2,…,xn進(jìn)行一個(gè)輪換后,布爾函數(shù)(1)的值不變,即

證明采用數(shù)學(xué)歸納法證明.

當(dāng)n=3時(shí),顯然有F3(x1,x2,x3)=F3(x2,x3,x1)=F3(x3,x1,x2)=x1x2x3;

當(dāng)n=4時(shí)也可以類似驗(yàn)證命題成立.假設(shè)n

下證當(dāng)n=m時(shí)命題成立.

再由(2)式可知,一方面等式的左端

另一方面,求證等式右端

上面公式左右兩端都等于4項(xiàng)的和,根據(jù)歸納假設(shè)可知,這4項(xiàng)分別對(duì)應(yīng)相等.所以當(dāng)n=m時(shí),命題也成立.綜上,命題成立.

定理2公式中函數(shù)具有性質(zhì)

證明

定理3布爾函數(shù)(1)都可遞歸展開(kāi)成一個(gè)析取主范式.

證明采用數(shù)學(xué)歸納法證明.

當(dāng)n=3,4時(shí)展開(kāi)式中的每一項(xiàng)恰好是布爾函數(shù)(1)的一個(gè)極小項(xiàng),結(jié)論顯然成立.

假設(shè)命題在n

推論1對(duì)序列x1,x2,…,xn進(jìn)行一個(gè)輪換后,布爾函數(shù)(1)的主范式不變.

定理4在布爾方程組(3)中,每個(gè)變量xi(1≤i≤n)至多在兩個(gè)方程中出現(xiàn);另外,如果某兩個(gè)方程中含有公共變量個(gè)數(shù)多于一個(gè),則這幾個(gè)變量相等.

證明從略(根據(jù)布爾變量的引入方式易得).

定理5如果在(3)中第i個(gè)和第j個(gè)方程含有一個(gè)公共變量xk,那么…,xn)=1的充分必要條件是.其中,

如果在上述表達(dá)式中,xk+1,xk+2,…,xn,x1,x2,…,xk-1某一變量沒(méi)有出現(xiàn),則其他變量依次遞進(jìn).

2.2 極大平面圖4-著色全部解算法

2.2.1 算法思想

2.2.2 算法步驟

步驟1)讀入表示極大平面圖的布爾方程組(3);

步驟2)判斷所有變量是否都已經(jīng)包含在唯一方程中,若是則轉(zhuǎn)步驟4,否則轉(zhuǎn)步驟3;

步驟3)選定變量xk,取出包含xk的兩個(gè)方程,利用定理5將其合并為一個(gè)方程,并用新方程代替原方程組中的這兩個(gè)方程,轉(zhuǎn)步驟2;

步驟4)根據(jù)定理3將每個(gè)方程左端的布爾函數(shù)遞歸展開(kāi)為一個(gè)析取主范式,得到每一個(gè)布爾函數(shù)的成真賦值.

2.2.3 收斂性分析

根據(jù)算法原理可知,程序每運(yùn)算一次可以消去一個(gè)方程,而每個(gè)變量至多包含在兩個(gè)方程中,所以如果(3)中含有n個(gè)變量,則至多運(yùn)算n次后,可將所有的變量化為只包含在唯一方程的情形,然后將每個(gè)方程遞歸展開(kāi)就得到了(3)的全部解,所以,該算法是在有限步驟內(nèi)收斂的.

[1] Appel K,Hakn W.Every planar map is four colo rable[J].Illinois JMath.1977,21(3):429-490.

[2] 烏力吉.平面圖的4-著色的簡(jiǎn)單布爾方程表示[J].內(nèi)蒙古大學(xué)學(xué)報(bào):自然科學(xué)版.2001,32(1):1-5.

[3] 邦迪JA,默蒂USR.圖論及其應(yīng)用[M].吳望名,譯.北京:科學(xué)出版社,1984.

[4] 烏力吉.平面圖正常4-著色數(shù)的一個(gè)計(jì)算公式[J].內(nèi)蒙古大學(xué)學(xué)報(bào):自然科學(xué)版.2001,32(2):119-124.

[5] 賀佩玲,黃元秋.W_4×S_n的交叉數(shù)[J].鄭州大學(xué)學(xué)報(bào):理學(xué)版,2009,41(1):6-9.

[6] 劉廣軍,劉信生.P_m∨W_n的點(diǎn)可區(qū)別全色數(shù)[J].鄭州大學(xué)學(xué)報(bào):理學(xué)版,2007,39(4):14-21.

[7] 楊愛(ài)峰,原晉江.圖的相鄰強(qiáng)邊著色數(shù)[J].鄭州大學(xué)學(xué)報(bào):理學(xué)版,2004,36(2):7-9.

[8] 董海燕,孫磊,孫艷麗.關(guān)于鄰點(diǎn)可區(qū)別全染色的幾個(gè)新結(jié)果[J].廣西師范大學(xué)學(xué)報(bào):自然科學(xué)版,2005,23(3):41-43.

[9] 唐高華,高艷艷,林光科.幾類簡(jiǎn)單圖的交換零因子半群[J].廣西師范大學(xué)學(xué)報(bào):自然科學(xué)版,2009,27(1):25-28.

The Maximum Planar Graph 4-Colorings Boolean Equation Group

JIA Yong-w ang, BA ILian-hua, U lji
(College of Science,Inner M ongolia University of Technology,Hohhot 010051,China)

The maximum p lanar graph 4-colorings Boolean equation group is studied,and some useful p roperties is obtained.A p roper 4-coloring algorithm is p rovided for maximal p lanar graphs.The algorithm can find all p roper 4-coloring solutions for any given maximal p lanar graph.

p lanar ganphs;maximal p lanar graph;4-colo ring;Boo lean equation group

O 157.5

A

1671-6841(2010)03-0037-04

2010-02-28

內(nèi)蒙古自然科學(xué)基金資助項(xiàng)目,編號(hào)200607010115.

賈永旺(1975-),男,講師,碩士,主要從事圖論與組合優(yōu)化研究,E-mail:jyw_zhy@sina.com.