图的着色问题

Published on 2016 - 06 - 22

地图染色与四色猜想

与平面图有密切关系的一个图论应用问题是图的着色。图的着色问题起源于地图染色问题和四色猜想。例如,对图13所示的美国地图,要给每个州染色,使得任何两个相邻的州颜色均不同。与S1相邻的州有S2~S7,要使得这7个州中任何两个相邻的州颜色均不同,至少需要使用3种颜色。图13给出了一个用3种颜色染色的方案:S1染为红色(r),S3、S5、S7染为绿色(g),S2、S4、S6染为蓝色(b)。现在的问题是,要给所有州染色,使得任何两个相邻的州颜色均不同,至少需要使用多少种颜色?

这个问题最早是由英国数学家弗南西斯·格思里(Francis Guthrie)于1852年提出来的。他发现有些地图能用3种颜色完成染色。他也发现,对所有地图,4种颜色就足以完成染色,但他无法证明。此后,“每张地图都能用4种或者更少的颜色来染色”这个猜想开始以四色猜想(Four Color Conjecture)而闻名,很多数学家都尝试着去证明它。四色猜想不止一次地被有的数学家宣称证明了,但又被其他数学家证明是错误的。

1976年,美国数学家阿佩尔(Kenneth Appel)与哈肯(Wolfgang Haken)在美国伊利诺斯大学的两台不同的电子计算机上,用了1200个小时,作了100亿个判断,终于完成了四色定理的证明,并在当年的美国数学学会的夏季会议上,向全世界宣布他们已经证明了四色猜想。值得一提的是,并不是所有的数学家都满意他们的证明。

图的着色

根据着色对象不同,图的着色问题(Coloring Problem)分为顶点着色、边着色、和平面图的面着色。前面介绍的地图着色实际上是平面图的面着色。

顶点着色

图的顶点着色(Vertex Coloring):给图G(图G中不存在自身环)的每个顶点指定一种颜色,使得任何两个相邻的顶点颜色均不同。

如果能用k种颜色对图G进行顶点着色,就称对图G进行了k着色(k-Coloring),也称G是k-可着色的(k-Colorable)。若G是k-可着色的,但不是(k-1)-可着色的,则称G是k色(k-Colormatic)的图,并称这样的k为图G的色数(Colormatic Number),记为χ(G)。所谓图G的色数,就是在对图G进行顶点着色时所用的最少颜色数。

关于顶点着色有如下一些结论和定理。

  • 定理11 χ(G)=1,当且仅当G为零图(即边集E(G)为空的图)。
  • 定理12 χ(Kn)=n。
  • 定理13 奇圈的色数为3。
  • 定理14 图G的色数是2当且仅当G是一个非空的二部图。
  • 定理15 对任意的图G(图G中不存在自身环),均有:χ(G)≤∆(G)+1。
  • 定理16(Brooks定理) 设连通图G不是完全图Kn,也不是奇圈,则χ(G)≤∆(G)。

试计算图14中各图的色数。

G1实际上是二部图,而由定理14可知,χ(G1)=2。χ(G2)=4。图G3是彼得森图,由布鲁斯定理可知,χ(G3)≤∆(G3)=3,又因为G3中有奇圈,所以χ(G3)≥3,因此χ(G3)=3。由布鲁斯定理可知,χ(G4)≤∆(G4)=4,又因为G3中有奇圈,所以χ(G4)≥3,因而χ(G4)为3或4,但试着用3种颜色去着色,发现是不可能的,所以χ(G4)只能为4。

边着色

图的边着色(Edge Coloring):给图G的每条边指定一种颜色,使得任何两条相邻的边颜色均不同。

如果能用k种颜色对图G进行边着色,就称对图G进行了k边着色(k-Edge Coloring),也称G是k-边可着色的(k-Edge Colorable)。若G是k-边可着色的,但不是(k-1)-边可着色的,则称G是k边色(k-Edge Colormatic)的图,并称这样的k为图G的边色数(Edge Colormatic Number),记为χ1(G)。所谓图G的边色数,就是在对图G进行边着色时所用的最少颜色数。

关于边着色有如下一些结论和定理。

  • 定理17(Vizing定理) 对于任何一个非空简单图G,都有:
χ1(G)=∆(G),或者χ1(G)=∆(G)+1

维津(Vizing)定理说明,对简单图G来说,它的边色数χ1(G)为∆(G)或∆(G)+1,但哪些图的边色数为∆(G),哪些图的边色数为∆(G)+1,至今还是一个没有解决的问题,只是对于一些特殊的图有一些结论,如定理18、19。

  • 定理18 设图G为长度大于或等于2的偶圈,则χ1(G)=∆(G)=2;设图G为长度大于或等于3的奇圈,则χ1(G)=∆(G)+1=3。
  • 定理19 对二部图G,有:χ1(G)=∆(G)。

试计算图15中各图的边色数。

因为G1中无奇数长度的回路,所以它是二部图,由定理19可知,χ1(G1)=∆(G1)=4。由维津定理可知,χ1(G2)为∆(G2)=4,或∆(G2)+1=5,又存在如图15(b)所示的4种颜色的边着色,所以χ1(G2)=4。

地图着色与平面图的面着色

地图实际上是一种平面图:平面图的区域(即面)代表国家,边表示国家之间的边界,顶点则是边界的交汇处。例如,对图16(a)所示的地图,在国家边界的每个交汇处放置一个顶点,对国家之间的每条边界用直线或曲线将对应的顶点连起来,就得到图16(b)所示的平面图。

对平面图G来说,它将平面分成r个区域(即面),现在对每个区域染色,使得有公共边的区域颜色均不同,这种染色称为平面图的面着色(Face Coloring)。如果能用k种颜色给平面图G进行面着色,则称G是k-面可着色的(k-Face Colorable),在进行面着色时,所用最少颜色数称为平面图的面色数(face Colormatic Number),记为χ*(G)。

平面图的面着色可以转换成其对偶图的顶点着色,依据是下面的定理20。

定理20 平面图G是k-面可着色的,当且仅当它的对偶图G*是k色的图。

例如,对图16(b)所示的平面图转换成其对偶图的过程和结果分别如图16(c)和图16(d)所示。在图16(d)中,因为存在奇圈,所以χ(G)≥3,并且因为∆(G)=3,根据定理5,可知χ(G)=4。图16(d)给出了用4种颜色着色的方案,图16(e)在对应的地图上用红色(r)、绿色(g)、蓝色(b)和黄色(y)4种颜色进行着色。

平面图面着色与四色猜想

前面已经提到过四色猜想,此处对四色猜想进一步描述。

四色猜想:连通简单平面图的色数不超过4。

这个猜想于1976年由Appel和Haken宣称证明了,当然,不是所有的数学家都满意他们的证明。事实上,大部分数学家都持很高的怀疑态度,并对这个证明很不满意。这引起了关于“什么是数学证明”的许多讨论。

尽管现在四色猜想还没有被完全证明,但已经能确定的是:连通简单平面图的色数不超过5,即以下的五色定理。

定理21(五色定理) 连通简单平面图G的色数不超过5。

图着色的应用

例2 考试安排问题——图的顶点着色

某高校有n门选修课需要进行期末考试,同一个学生可能选修了多门课程,但他不能在同一时间段参加两门课程的考试。问该校的期末考试至少需要安排几个时间段。

例如,假设需要安排7门课程的期末考试,课程编号为1~7,已知以下课程之间有公共的学生选修:

(1,2)、(1,3)、(1,4)、(1,7)、(2,3)、(2,4)、(2,5)、(2,7)、(3,4)、(3,6)、(3,7)、(4,5)、(4,6)、(5,6)、(5,7)、(6,7)

很显然,可以以课程为顶点来构图,如果两门课程之间有公共学生选修,则在这两门课程之间连边。构造好的图如图17所示,问题转换成求图的顶点着色,每种颜色的顶点安排在同一个时间段考试。该图的色数为4,因此需要安排4个时间段:Ⅰ—课程1,Ⅱ—课程2、6,Ⅲ—课程3、5,Ⅳ—课程4、7。

图着色求解算法及例题解析

需要说明的是,尽管有很多定理来判定图的色数、边色数,但求图的色数、边色数以及具体的着色方案并没有有效的算法。本节介绍一种求χ(G)的近似有效算法——顺序着色算法。

设图G的顶点数为n,要求对图G进行顶点着色,步骤如下。

  1. 用i表示顶点序号,i=1。
  2. 用c表示给顶点i着色为第c种颜色,c=1;
  3. 对第i个顶点着色:考虑它的每个邻接顶点,如果都没有使用第c种颜色,则给顶点i着色为第c种颜色,并转第5步;只要有一个顶点使用了第c种颜色,则转第4步;
  4. c=c+1,并转第3步;
  5. 若还有顶点未着色,则i=i+1,并转向第2步,否则算法结束。

顺序着色算法实际上是采取了一种贪心策略:在给任何一个顶点着色时,采用其邻接顶点中没有使用的、编号最小的颜色。

以对图18(a)所示的图G进行顶点着色为例解释顺序着色算法的执行过程。在图18(b)中首先给顶点x1着色为第1种颜色;然后在图18(c)中对顶点x2进行着色,因为它的邻接顶点中已经使用了第1种颜色,所以给x2着色为第2种颜色;在图18(d)中对顶点x3进行着色,因为它的邻接顶点中没有使用第1种颜色,所以给顶点x3着色为第1种颜色;……;在图18(h)中,对最后一个顶点x7进行着色,它的邻接顶点中,使用了第1、3种颜色,所以给顶点x7着色为第2种颜色,至此着色完毕,求得χ(G)=3,并求得一个着色方案。

顺序着色算法与顶点的着色顺序有密切的关系,这就是为什么叫顺序着色算法的原因。例如,考虑图19(a)所示的二部图,若按x1,x2,x3,x4,y1,y2,y3,y4顺序执行该算法,则只需用两种颜色进行着色,如图19(b)所示。但如果按x1,y1,x2,y2,x3,y3,x4,y4顺序执行该算法,则需用4种颜色进行着色,如图19(c)所示。因此,顺序着色算法并不一定有效。

接下来通过一道ACM/ICPC例题,讲解有关顶点着色问题的求解和顺序着色算法的程序实现。

例3 频道分配(Channel Allocation)

题目来源:

South Africa 2001, ZOJ1084, POJ1129

题目描述:

当一个广播站向一个很广的地区广播时需要使用中继器,用来转发信号,使得接收器都能接收到足够强的信号。然而,每个中继器所使用的频道必须很好地选择,以保证相邻的中继器不会互相干扰。要满足这个条件,相邻中继器必须使用不同的频道。

由于广播频率带宽是一种很宝贵的资源,对于一个给定的中继器网络,所使用频道数量应该尽可能少。编写程序,读入中继器网络的信息,计算需要使用频道的最少数目。

输入描述:

输入文件中包含多个测试数据,每个测试数据描述了一个中继器网络。每个中继器网络的格式如下。

  1. 第1行为一个整数N,表示中继器的数目,1≤N≤26,中继器用前N个大写字母表示,例如,假设有10个中继器,则这10个中继器的名字为A,B,C,…,I和J。
  2. 接下来有N行,描述了这N个中继器的相邻关系,第1行描述和中继器A相邻的中继器,第2行描述和中继器B相邻的中继器;等等。每行的格式为:
A:BCDH

表示和中继器A相邻的中继器有B、C、D和H(按字母升序排列)。如果一个中继器没有相邻中继器,则其格式为:

A:

注意:相邻关系是对称的,A与B相邻,则B也与A相邻;另外,中继器网络是一个平面图,即中继器网络所构成的图中不存在相交的边。

输入文件最后一行为N=0,表示输入结束。

输出描述:

对每个中继器网络,输出一行,为该中继器网络所需频道的最小数目。

分析:

很明显,本题要求的是图G的色数χ(G)。样例输入中第2个测试数据所描述的中继器网络如图20所示。本题采用前面介绍的顺序着色算法求解,例如在图20(c)中给顶点C着色时,它的邻接顶点中,顶点D和F目前没有着色,顶点B着色为第1种颜色,所以给顶点C着色为第0种颜色。最终的着色方案如图20(d)所示,求得的χ(G)为4。

代码如下:

参考文档