图的点染色和边染色

书籍:现代科技综述大辞典上 更新时间:2018-11-16 21:24:16

出处:按学科分类—自然科学总论 北京出版社《现代科技综述大辞典上》第28页(4555字)

在组合论中常借用颜色使研究对象具有某特征或作出某种分类,“涂色”常泛指没有附加条件地将色分派给研究对象。

典型问题如:正方形4顶点用黑白2色任意涂色,可有6种不同图象(全白、全黑、3白1黑、3黑1白、2白2黑同色相邻或相间)。完全图K6的边红蓝2色任意涂色,必有同色边的K3(拉姆齐Ramsey数R(3,3)=6)。

图论中研究对象(点和边)的色分派常要求满足附加条件,故改术语为染色。

图G=(V,E),|V|=n,|E|=m,(n个点,m条边)。

除非特别标明,一般研究无多重边,无自环的标之为简单图的图,本文也是。图G的顶点染色,是对每一点指派一种颜色,使相邻接的点都有不同的色(或称正常点染色,经常简称染色)。

如给定k种色,可以用λ(λ≥k)种色作出正常点染色,就说G是k-可(点)染色,使G有正常染色的最小色种数称为(点)色数,记为x(G),对于k-可染色图,必有x≤k,如记x(G)=k,则说G是k色的。

求图的色数意义深远。

众所周知的四色猜想说:在平面(球面)上(每个国家认为由一个单连通区域表出,两国相邻即有一段公共边界线,任何地图能够只用4种色染色,使没有两邻国有相同色。图论中采用改造成对偶图的方法:每个区域缩为1个“代表点”,2个有公共边界的代表点之间连接一条“边”,平面地图就对偶了1个由“代表点”和“边”组成的平面图(地图的对偶图)。这个对偶图的点染色就是地图的面染色。

四色猜想的本意就是认为:每一个可平面图是4-可点染色的,早期研究这猜想的有莫比乌斯(Möbius,1840)、格思里(Guthrie,1850)、德·摩根(De Morgan,1850)。

肯普(Kempe,1879)曾给出猜想的许多错误“证明”中的第1个“证明”,实际上,Kempe的链路方法证得的是“五色定理”。希伍德(Heawood,1890)指出了他的错误,直到1976年美国的阿倍(K.Appel)、黑肯(W.Hakan)和考奇(J.Koch)3人用电子计算机证明了四色定理,有不少学者认为首开了机器证明的范例。也有不少学者认为不严密,不予承认。总之,还有相当一些人仍在探索简明的证明。当然,确定点色数是基本问题。已求得:x(Kn)=n,x(Kn-e)=n-1,,x(Kp,q)=2,x(C2i)=2,x(C2i+1)=3。科尼希(König)1931年证明了一个图是双色的,当且仅当它不含奇圈。但是3-可色图的特征还没有解决。

已经求得一些估界,记Δ为最大的点度粗略的有x≤1+Δ。

对于Δ≥3的图,估式x≤Δ(除了KΔ+1作为G的分支以外)成立。由贝克霍夫(Birkhoff,1912)作为冲击四色猜想而引入的色多项式也是求色数的工具,记P(G,λ)为一个标定图至多用λ种色(点)染色的不同方式个数。它也是λ的一个整系数多项式。

当λ<x(G)时,P(G,λ)=0,使P(G,λ)>0的最小正整数就是x(G)。四色猜想断言:可平面图G,P(G,λ)>0。易于看出P(Kn,λ)=λ(λ-1)…(λ-n+1)=λ(n)。任何一个非完全图G,若u,v是非邻接点,则

P(G,λ)=P(G+uv,λ)+P(Gu=v,λ)

式中G+uv表示添加uv边后的图,Gu=v表示等同u、v二点所得的图,它变成n-1个点的图了。

多次递归使用P(G,λ)就等于若干完全图的色多项式之和。与此逐次加边方式相仿,还有逐次减边方式求P(G,λ)的,如G中有邻接边uv,P(G,λ)=P(G-uv,λ)-P(Gu=v,λ),多次递归使用,P(G,λ)等于若干孤立点图色多项式的代数和。

色多项式系数表征了图的结构之间的内在性质:P(G,λ)=λn-mλn-1+…+(-1)n-papλp,即n个点m条边p个连通分支的图的色多项式必是首系数为1,λn-1系数为-m,以下均正负交替。最低非零次项是λp,里德(R.C.Read,1968)猜想:P(G,λ)的系数绝对值是单峰性的,即先上升后下降。

同构的图,色多项式相同,反之,不一定。已证出,一个有n个点的图G是一棵树当且仅当P(G,λ)=λ(λ-1)n-1

而4个点的树就有不同构的P4和星K1,3,一般的具有相同色多项式的图的特征还没有解决。另一难题是如何判断多项式是否是某个图的色多项式。

色多项式作为研究色数的工具还有很多潜在的成果待开拓,图论作为离散数学范畴,没有“万能”或通用的研究手段,如数学分析中有成熟手段:极限,微分,积分,级数等。图论中邻接矩阵特征多项式,再借用线性代数和近世代数中已有成果,发展成称为“代数图论”的分支。

色多项式研究正在发展中,点染色另外的研究方向有唯一可染色图问题[用x(G)种色对V(G)作的色划分是相同的]、色临界问题[对G中每一点v,都有x(G-v)=xLG)-1称为临界图]。

在理论计算机科学研究领域,算法复杂性是基本概念,它对现实的指导意义深远。只有运算次数是求解问题规模n的多项式,这个算法才是可行的,不然发生指数爆炸,一般都效果不好,尤其是一类称之为NP-完全型难题在现在计算机结构体系下是难以找到有效算法的,已经证明,对任意的图G=(V,E),欲判断G是不是3-可染色是一个NP-完全问题(斯托克迈耶stockmeyer,1973证出)。

图G=(V,E)的边染色,即对图的每条边指派一种色且使得没有两条邻接边有相同色,G中同色的边集也可称为(色)边独立集(匹配),使G有边染色的最小色种个数称为边色数,记为x′(G),记Δ是G的最大度,维津(Vizing)在1964年证出Δ≤x′(G)≤Δ+1,此后称x′(G)=Δ的为第1类图C1,其余的,归入第2类图C2

并引出了对边色数分类的大量研究,已证得属于C1的图类有:二分图,完全图K2i等,属于C2的图类有K2i+1,C2i+1等。但通用图的分类还没有找到判据。已有人对143个连通的6个顶点以下的图分类,仅有8个属于C2,这8个图中有C3,C5,K5,K5-e等。

厄尔丢斯(Erdös)和威尔逊(wilson)在1977年证明n个点的图中,c1类图占的比值,随n→∞趋于1,分类问题中还有不少充分性定理,如对于正则图,如m>Δ·,则G属于C2类,另一个有趣的结论:四色定理等价于3正则平面图的边色数为3,它显示了“点”染色与“边”染色之间的内在联系。

边色数的另一研究方向是边色临界图,如果G是连通的且属于C2类,对于任一条边e,有x′(G-e)<x′(G),则G称(边色)临界图,或说是Δ-边色临界的,如奇圈C2i+1是2-边色临界的,K5-e是4-边色临界的,这方面已证得一些必要条件:如果G是Δ-边色临界的,则G不含割点;记I是G的任意一个边独立集,则x′(G-I)=x′(G)-1;对于满足2≤i≤Δ的每个i,G含有一个i-边色临界子图;如v和w是G中邻接点,则必有d(v)+d(w)≥Δ+2;不存在正则的Δ-边色临界图,满足Δ≥3。

关于边染色又引出不少猜想,贾柯勃逊(Jakobsen,1974)、比耐克(Beineke)和威尔逊(wilson)在1973年猜想(因子分解猜想):每一个偶数点的边色临界图含有一个1-因子;每一个边色临界图含有一个2-因子(k-因子即每点的度为k的生成子图。

维津在1968年猜想:△-边色临界图必有

另一研究方向是唯一(边)染色图,即G的边集在x′(G)种色边染色下,色划分是唯一的那些图。此时G也称为x′-唯一边可色图。

对此已证得唯一边可色图的必要条件:(1)每条色边都和其它色的一条边邻接。

(2)记H(α,β)为G中α色和β色的边导出双色子图,则H(α,β)或是开路,或是闭偶圈。(3)满足不等式:

(4)如G还是k-正则图(k≥3)),若G中对任取的一条边插入一个点(一次细分)所得的图记为H,则H是3-临界的,此外还证得仅有的4-边色临界图是K1,4

在唯一边可色图研究领域内有不少猜想,猜想(1)每一个平面唯一3-可边染色图,除了K1,3外,都含一个三角形;猜想(2)非平面的3正则唯一3-边可染色图,只有一个彼得森(peterson)型图P(9,2),即外圈是依次标点为1,2,…,9的C9,每点向内延伸一条边,加一个点,相应记为1’,,2’,…,9’,。而且这9个点隔号相连形成另一个C9:1’3’5’7’9’2’4’6’8’1’;猜想(3):每一个恰有3个哈密顿圈的3正则图是唯一3-边可染色的。

在边染色问题中,中国学者引入了边-色多项式,记为

Q(G,λ)=λm-a1λm-1+a2λm-2-…+(-1)kakλm-k

其中.di为每点的度,(Δ),N(Δ)为G中三角形个数。

m-k=p(G),是G的连通分支数。如果两个图点数相同且边色多项式也相同就能得出两个图同构,则说这个图是边色多项式拟色唯一的。已推知边色多项式拟色唯一的图有:Pn;Kn;Kn,n;Tn(n≤5的树),而对于点数n>5的树,其边色多项式Q(Tn,λ)不是拟色唯一的(唐廷载、韩绍岭,1991)。

在点染色、边染色基础上,1965年有人把点和边结合看待,提出了“全染色”概念,一个图的全色数x2(G)是对图的点、边进行色分配,使既是点染色又是边染色并且点和关联边不同色的最小色种个数,如x2(K3,3)=5。比扎特(M.Behzad)1965年猜想:对任何图,x2(G)≤Δ(G)+2.边染色在电网络,课程表问题,拉丁方构造等领域也获得应用。

关于对任意一个图,实施正常点染色,或边染色的有效算法或近似算法是重要的课题,关于全染色,多重图,超图等元素染色在理论和应用方面还有大量工作等待人们去研究。

【参考文献】:

1 Beineke L W,et al.Selected topics in graph theory,1978,103~126

2 Yap H P.London Mathematical Society lecture Note Series,1986,108~887

3 唐廷载,等.数学研究与评论,1991.11(4)∶522

(北京理工大学杨骅飞副教授撰;孙良审)

分享到: