第九章 图的着色ppt课件.ppt

第九章 色数,图的点着色数着色数的基本性质Brooks定理图的边着色数地图着色问题,问题来源,图的着色问题是由地图的着色问题引申而来的：用m种颜色为地图着色，使得地图上的每一个区域着一种颜色，且相邻区域颜色不同。问题处理：如果把每一个区域收缩为一个顶点，把相邻两个区域用一条边相连接，就可以把一个区域图抽象为一个平面图。,问题来源,例如，图9-1（a）所示的区域图可抽象为9-1（b）所表示的平面图。19世纪50年代，英国学者提出了任何地图都可以4种颜色来着色的4色猜想问题。过了100多年，这个问题才由美国学者在计算机上予以证明，这就是著名的四色定理。例如，在图9-1中，区域用城市名表示，颜色用数字表示，则图中表示了不同区域的不同着色问题。,区域和点的对应,5,四色问题(Four Color Problem),1852, Francis Guthrie, 注意到英格兰地图可以用4种颜色染色, 使得相邻区域(有一段公共边界,不只是有一个公共点)有不同颜色; 他问其弟 Frederick 是否任意地图都有此性质? Frederick Guthrie DeMorgan Hamilton. 1878, Cayley, 提交伦敦数学会.,Francis Guthrie的猜想,给地图的每个区域着色，保持任何有公共边界的区域使用不同颜色，只要四种颜色就够了。,很容易证明，三种颜色是不够的 - Guthrie, de Morgan,可以证明：任何地图不会有这样的构型：5个区域，每个均与其它4个相邻。误认为这蕴涵四色猜想导致许多错误证明上图中没有4个区域两两都相邻，但三色不够。,7,四色问题(Four Color Problem),8,四色问题(Four Color Problem),1879, Kempe, 第一次“证明”1880, Tait, 另一个“证明” 1890, Heawood 发现Kempe证明的错误1891, Petersen发现Tait证明的漏洞(Tait猜想)1946, Tutte发现Tait证明的错误(Tait猜想反例),9,四色问题(Four Color Problem),1913, Birkhoff, 一个大贡献1922, Franklin, 证明不超过22个区域的地图四色猜想成立1950,不超过35个区域1960,不超过39个区域其他人取得其他形式进展:1974,52区域,10,四色问题(Four Color Problem),1936-50,Heesch,最终解决问题的两个要素: 10000个情形,100年约化(reducibility), 放电(discharging). 1972-76, Appel, Haken, 1482个情形, IBM360, 1200小时, 论文139页+400页程序, conjectureagnogramstheorem,11,四色问题(Four Color Problem),12,四色定理的意义,“四色问题”的被证明不仅解决了一个历时100多年的难题，而且成为数学史上一系列新思维的起点。在“四色问题”的研究过程中，不少新的数学理论随之产生，也发展了很多数学计算技巧。如将地图的着色问题化为图论问题，丰富了图论的内容。不仅如此，“四色问题”在有效地设计航空班机日程表，设计计算机的编码程序上都起到了推动作用。,应用背景示例,问题1：排考试时间，一方面要总时间尽可能短(假设教室没问题)，另一方面一个同学所学的任意两门课不能同时考。问题2：仓库存放若干种化学制品，其中某些制品相互接触有可能引发爆炸，为预防事故，将其隔间存放。要达到安全要求，至少将该仓库隔成多少间？,图的着色,通常所说的着色问题是指下述两类问题： 1给定无向图G=(V,E)，用m种颜色为图中的每个顶点着色，要求每个顶点着一种颜色，并使相邻两顶点之间有着不同的颜色，这个问题称为图的顶点着色问题。 2给定无环图G=(V,E)，用m种颜色为图中的每条边着色，要求每条边着一种颜色，并使相邻两条边有着不同的颜色，这个问题称为图的边着色问题。,9.2 顶点着色,定义9.2.1 给定简单图G及一有限集合C=c1,c2,cn, 用C中元素给G中每个顶点指定一个标号，使得任何相邻顶点的标号不相同，则称为给G做一个点着色。诸ci (i=1,2,n) 称为“颜色”。如果图G可以用n种颜色着色，则G称为n-可着色的。使G是n-可着色的最小的n称为G的着色数，记为(G)。若(G)=n，则称G是n-色图。,16,点色数性质,(G)=1 G是零图 (Kn)=n(G)=2 G是非零图二部图G是2-可着色 G是二部图 G无奇圈(Cn)= 2, n偶数 (Wn)= 3, n奇数 3, n奇数 4, n偶数,二部图的着色数,设G中至少含一条边，则(G)=2当且仅当G是二部图。 若(G)=2，则将一种颜色的顶点放在一起作为V1,将另一种颜色的顶点即放在一起作为V2 ，构成二部图。, 若G是二部图，每个二部划分中的顶点可以着一种颜色。,18,二部图判定,n(n=2)阶无向图G是二部图当且仅当G中无奇圈当且仅当G是2-可着色 。,与点着色数有关的几个“常识”,(G)|VG|, 且等号当且仅当G=Kn时成立。设H是G的子图，若(H)=k, 则(G)k。若d(v)=k, 则与v相邻的k个顶点着色至多需要k种颜色。图G的着色数等于其着色数最大的连通分支的着色数。,（1）若图G是二分图，则(G)=2。,临界图,定义：若图G的着色数是k, 但vVG, (G-v)k, 则称G是k-临界图。,临界点与临界图,定义9.1.3：设G是图，vV(G)，若(Gv) (G)， 则称v是临界点。若G的每个点都是临界点，则称G是临界图。,G是k-临界图即：G的着色数是k, 但G的任何真子图的着色数均小于k。任何k-色图必含有k-临界子图。如果G是k-临界图，G一定是连通图。注意：G一定有着色数是k的连通分支。,黄绿对换,可空出黄色,一个4-临界图的例子,外围的奇回路必须用3色,Grtzwch 图,临界图的性质:,1、图G中的顶点v是临界点，当且仅当(Gv) = (G)1。2、若顶点v是图G的一个临界点，则有d(v) (G)1 .3、若G是临界图，则有(G) (G)14、任何p阶图G都含有一个临界的导出子图H，使得(H) = (G)。,临界点使色数减一,性质1：图G的顶点v是临界点，当且仅当(Gv)=(G)1。证明：若(Gv) =(G)1 ,则(Gv) (G)，即v是临界点。 反之，若v是临界点，则(Gv)(G)，即(Gv) (G)1。如果(Gv) (G)1，则有 (Gv) (G)2，于是Gv有一个正常(G)2) 着色，从而G也就有一个正常(G)1 )着色。此与(G)的定义相矛盾。故(Gv) = (G)1。,临界点的度不小于色数减一,性质2：若顶点v是图G的临界点，则有d(v)(G)1。证明；由性质1，Gv有正常(G)1)着色。 若d(v)(G)1，则在的(G)1种颜色中至少有一种颜色i，使得任何与v邻接的顶点u，(u) i 。于是，可以在G中将v着颜色i，其余顶点的着色与相同，这样就得到了G的一个正常(G)1)着色，此与 (G)的定义相矛盾。故d(v)(G)1。,临界图最小度不小于色数减一,定理10.1.2：若G是一个临界图，则(G) (G) 1 。证明：由性质2知，任意临界点v，都有d(v)(G)1。 故临界图G中所有顶点的度都不小于色数减一，所以(G) (G) 1。,图有同色的临界导出子图,定理10.1.3：任何p阶图G都含有一个临界的导出子图H，使得(H) = (G)。证明：对p用归纳法。 归纳基础：p=1时显然成立。 归纳步骤：设对p1个顶点的图结论成立。G是p阶图，若任何vV(G)， (Gv) = (G)1 , 则G本身是一个临界图；否则，有uV(G)，使(Gu)=(G)。由归纳假设，Gu含临界的导出子图H , 且(H)=(Gu)=(G)，而H也是p阶图G的临界的导出子图。由归纳法知，定理成立。,K色图中顶点的度,推论9.1.1：任何k色图中至少有k个顶点的度不小于k 1。证明：设(G)=k，H是G的一临界子图，则有 (H)=(G)=k。由定理9.1.2可知，(H)(H)1，因为H是k色的，所以H中至少有k个点，又因为对任意的vV(H) , 有dG(v)dH(v)(H)k1。故结论成立。,定理9.1.4：对任何图G，有 (G) (G)+1， 这里(G)表示图G的最大度。证明：假设(G) (G)+2。 令(G)=k。由推论9.1.1，G至少有k个顶点的度不小于k1，即大于等于(G)+1。因(G)0，所以G中有度大于(G)的顶点，此与(G)定义矛盾。结论成立。注意此定理与定理9.1.2的区别。(定理9.1.2：若G是一个临界图，则(G) (G) 1。),Brooks定理 若连通图G不是完全图Kn(n3), 也不是奇圈，则： (G)(G),对Petersen图应用上述结果，得到(G)3,G：uv ( u，v着一样的颜色时) 表示u，v在G中不邻接，将这两个顶点对粘,G+uv ( u，v着不一样的颜色时) 表示u，v在G中不邻接，将这两个顶点连接,G：uv 表示u，v在G中不邻接，将这两个顶点对粘,定理1 设u和v是图G中两个不相邻的顶点,则 (G)=min(G+uv), (G：uv)其中G:uv是把G中顶点u与v重合成一个新顶点，且G中分别与u与v关联的边都与该新顶点关联。,证明:记e=uv,（1）设(G)=k,并考虑G的K着色.假设顶点u与v染不同的颜色,则G的k着色也是G+e的k着色.此时(G+e)k=(G).现假设顶点u和v的染色相同,则G的一个k染色可得到G:e的一个染色.故(G:e)k=(G).又在G的k染色中,或者u与v染为不同的颜色,或者为相同的颜色,故 min(G+uv), (G:uv) (G).,（2）G是G+e的子图,显然(G) (G+e). 设(G:e)=k1,并把结点u和v重合所得的新结点记为y,则在G:e的k1着色中,把分配给y的颜色分配给G中u和v(u,v不相邻),即可得到G的一个k1着色.故 (G)k1= (G:e) 所以(G) min(G+e), (G:uv). 综（1）（2）所述,有 (G)=min(G+u,v), (G:uv).,着色数与顶点次数,若G是k-临界图，则(G)k-1。(即：G中任一顶点的度数不小于k-1)证明：假设存在vV, 满足deg(v)k-1，则与v相邻的顶点最多用上k-2种颜色。 G是k-临界图，G-v一定可以用k-1种颜色着色，则其中至少有一种颜色未用于v的邻点，因此G也可以用k-1种颜色着色，与G是k-临界图矛盾。k-色图G中至少有k个顶点的度数不小于k-1。证明：G必含k-临界子图H，则(H)k-1，而|VH|k。,点着色数的下限,对于任意的无环图： (G)n/(n-) 其中n=|VG|, 是G中最小顶点度数。证明：vVG, 与v不相邻的顶点最多n-1个，如果给G正常着色，同颜色的顶点最多n-个，(n-)(G)n,求着色数的例子,上左：二部图 （图中无奇回路）上右：轮下左：有奇回路， =3，=3下右：有奇回路， =4，但不可 能是3,考试时间表编排问题的解,建立图模型每一个顶点对应为一门考试，任何两点相邻当且仅当至少有一个学生必须参加该两点所对应的两门考试。(因此，该两门考试必须安排在不同的时间)问题的解上述图的一个着色对应于考试时间表编排问题的一个解。上述图的着色数即所需要的最少时间段数。,42,应用示例1,某大学计算机专业三年级有5门选修课，其中课程1与2， 1与3， 1与4， 2与4， 2与5， 3与4， 3与5均有人同时选修，问安排这5门课考试至少需要几个时间段？,图着色法：例：用韦尔奇鲍威尔法对图着色（1）将图中顶点数依照度数的递减次序进行排列； 上图根据顶点度数以递减排列次序为： (6) (5) (5) (4) (4) (4) (3) (3),三、顶点着色的算法:穷举法韦尔奇鲍威尔（Welch.powell）着色法,（2）对5及与5不相邻的顶点1着蓝色；（3）对3和与3不相邻的顶点4、8着红色,对7和与7不相邻的顶点2、6着黄色，着色完毕。,图的边着色数,相关定义设G是无环图，给G的每个边着色，使得没有任何相邻的两边的颜色相同，称这样的着色为一种边着色。如果图G可以用k种颜色进行边着色，则G称为k-边可着色的。使G是k-边可着色的，但不是k-1边可着色的，则称k是G的边着色数，记为(G)。,例子,若图G是k边可染的，而lk，则G也是l边可染的。使图G具有正常边染色的最小颜色数，称为G的边色数，记作(G)。(G) (G),边色数=3,边色数=5,边的着色问题可以转化为顶点的着色问题。,妖怪图（snark graph） 妖怪图每个点都关联着3条边，用4种颜色可以把每条边涂上颜色，使得有公共端点的边异色，而用3种颜色办不到，切断任意3条边不会使它断裂成2个有边的图。,单星妖怪和双星妖怪：,边着色数的估计,简单图：(G)(G) (G)+1(Vizing定理)偶回路： (G) =2 (n2)奇回路： (G) =3 (n3)轮：(Wn)=(Wn)=n-1二部图：(G) =(G),图按边色数分为两类,由定理9.2.1，任何图G的边色数(G),要么是(G) ，要么是(G) +1。满足 (G) =(G) 的图称为第一类图。满足(G) = (G) +1的图称为第二类图。目前还没有一般的方法来判断一个图G属于哪一类。,定理(Vizing 1964)：若图G为简单图，图中顶点最大度为d，则G的边色数为d或d+1。,第一类图,第二类图,习题,1、证明petersen图的边色数为4。,练习,2、证明：若G是奇数阶的正则简单图，且q0，则(G )=(G) +1证明：因为p为奇数，故G的任一正常的边着色的每一色类最多是(p-1)/2条边，从而(G )(p-1)/2q又G为正则图，从而q=(G)p/2 故(G )(G) 由Vizing定理(G ) (G) +1故(G )=(G) +1,57,面着色与对偶图点着色,定理9: 地图G可k-面着色 对偶图G*可k-着色. 定理9: 连通无环平面图G可k-面着色 对偶图G*可k-着色. 研究平面图面着色研究平面图点着色,DEFINITION A coloring(着色)of a simple graph is the assignment of a color to each vertex of the graph so that no two adjacent vertices are assigned the same color.,五色定理(Heawood,1890)：用种颜色可以给任何简单连通平面图着色。证明：对顶点数v用归纳法 a)当v1，2，3，4，5时显然成立。 b)设vk时成立，现考察vk+1 已知必存在顶点u，使deg(u)5，在图G中删去u，得到G-u，由归纳假设知G-u可以用5种颜色着色。,定理2（五色定理）连通简单平面图G的色数为不超过5.,证明:对图的顶点数n作归纳. n5时,结论显然.若n-1个顶点时结论成立.下证有n个顶点时结论也成立.由于G是平面图,则(G) 5.故在G中至少存在一个顶点v0,其度数d(v0) 5.在图中删去顶点v0得图G,由归纳假设知G的色素为5.然后将v0又加回去,有两种情况:(1)d(v0)5或d(v0)=5但和v0邻接的5个结点的颜色数小于5.则v0极易着色,只要选择与四周顶点不同的颜色着色即可.,(2)d(v0)=5且和v0邻接着的5个结点着的颜色的是5种颜色,如下图(a)所示.称G中所有红黄色顶点为红黄集,称G中所有黑白色顶点为黑白集.故又有两种可能.(i)v1和v3属于红黄集导出子图的两个不同块中,如下图(b)所示.将v1所在块的红黄色对调,并不影响G的正常着色.然后将v0着上红色,即得图G的正常着色.,(a),(b),(ii)v1和v3属于红黄集导出子图的同一块中,则v1和v3之间必有一条属于红黄集的路P,P加上结点v0可构成圈C:v0v1pv3v0,如下图所示.由于C的存在,将黑白集分成两个子集,一个在C内,一个在C外.于是问题转化为(i)的类型,对黑白集按(i)型的办法处理,即得图G的正常着色.,(b),(c),(a),第五节 图着色的应用,贮藏问题:某工厂生产n种化学制品c1,c2,cn,其中某些制品是互不相容.若它们相互接触,则会发生化学反应甚至引起爆炸,为安全起见,该工厂必须把仓库分成若干隔间,以便把不相容的化学制品储藏在不同的隔间,试问该仓库至少应分成几个隔间?解:构建简单图G=,其中V(G)=c1,c2,cn 边ci,cjE(G)化学制品ci与cj互不相容. 易知,仓库的最少隔间数等于图G的色数(G).,电视频道分配问题,某地区内有n家电视发射台T1,T2,Tn.主管部门为每家电视发射台分配一个频道.为排除干扰,使用同一频道的电视台之间的距离必须大于指定的正数d,试问该地区至少需要多少频道? 构建简单图G=,其中V(G)=T1,T2,Tn 边Ti, TjE(G)Ti与Tj之间距离d. 易知,需要的最少频道等于图G的色数(G).,考试安排问题,某高校有n门选修课程v1,v2,vn需要进行期末考试.同一学生不能在同一天里参加两门课程的考试.问学校的期末考试需要几天? 构建简单图G=,其中V(G)=v1,v2,vn 边vi, vjE(G)vi与vj被同一同学选修. 故考试需要的最小天数等于图G的色数(G).,例：大学中7门考试，以下课程中有公共学生，12；13；14；17；23；24；25；27；34；36；37；45；46；56；57；67；问如何在尽可能少的时间段里安排7门考试并使得没有学生在同一时间里有两门考试。,时间段 课程 1 1 2 2，6 3 3，5 4 4，7,五色定理,为了给任何一张平面地图着色，保证有公共边界的区域颜色不同，最多只需要五种颜色就够了。证明要点：在简单平面图中，一定存在度数不大于5的顶点。对顶点个数归纳: (当n5, 结论显然成立); 归纳的图示如下：,v,3,1,2,4,5,v,3,1,2,4,5,?,有多少种正常着色？,如果用红、绿两色对右边的两个图进行点着色，能有几种不同的着色呢？,G1,G2,A,B,C,A,B,C,很容易看出，图G1只有两种不同的着色；而图G2可以有四种不同的着色。,问题：若对一个给定的标定图G，用t种颜色，进行正常着色，会有多少种不同的着色方案呢？,最多t色的正常着色数目.,定义10.3.1：设G是一个标定图，G的一个t种或不到t种颜色的正常着色称为G的一个最多t色的正常着色.令f(G, t)表示图G的不同的最多t色的正常着色之数目。给定图G，f(G, t)是t的一个函数。我们简称 f(G, t)为正常着色数目。,简单情况的正常着色数目,若t (G)，则f(G, t) = 0。从而，(G) = mint | f(G,t) 0。对完全图Kp，显然有 f(Kp,t) = t(t1)(t2) (tp+1) ;对由p个顶点组成的零图 Kp，显然有：f(Kp , t) = tp .,色多项式,设G是p个顶点标定的完全图，用t种颜色对G的顶点进行染色。当tp，G不存在t-正常染色。当tp，对G进行t-正常染色的方法数为t(t-1)(t-2) (t-p+1)。设G是由p个孤立点构成的标定图，那么对G进行t-正常染色的方法数为t p。一般地，对于给定的p阶标定图G，对其进行t-正常染色的方法数是t的一个函数，可以表示成t的一个多项式，称为图G的色多项式，记为f(G,t)。,给定图G，设u,vV(G)，e=(u,v) E(G)，对于G-e进行t-正常染色，这种染色分为两类：一类是u,v颜色不同，它与图G的正常染色是一一对应的；另一类是u,v颜色相同，它与Ge的正常染色是一一对应的，因此有f(G-e,t)=f(G,t)+f(Ge,t),f(G,t)= f(G-e,t)-f(Ge,t)f(G,t)= f(G+e,t)+f(Ge,t),色多项式的递推运算,+,+,+,=,=,=,=,t4-3t3+3t2-t,色多项式的递推运算,=t(t-1)(t-2)(t-3)(t-4)+3t(t-1)(t-2)(t-3)+t(t-1)(t-2)=t5-7t4+18t3-20t2+8t,=,=,=,+,+2,+,+3,+,色多项式的相关定理,定理6.17 对于任何p阶图G，f(G,t)都是t的整系数p次多项式，首项为t p，常数项为0。而且各项系数的符号正负相间。定理6.18 若G有k个连通分支G1, G2, ,Gk，则,定理6.19 设(p,q)图G有k个分支G1, G2, ,Gk，记f(G,t)=aiti，则有(1)ap=1；(2)ap-1=-q；(3)非零系数的最低次幂指数为G的连通分支的数目。,色多项式的相关定理,定理6.23 p阶图T是树，当且仅当它的色多项式f(T,t)=t(t-1) p-1推论6.24 设G是p个顶点的回路Cp(p3)，那么f(G,t)=f(Cp,t)=(t-1) p+(-1) p(t-1),Dual graph(对偶图)Each region of the map is represented by a vertex. Edges connect two vertices if the regions represented by these vertices have a common border.,G中每条边对应与G中的一条边，与G中割边对应的是环，可以将G中每条边画成只与它对应的边相交，与任何其它G或G中的边均不相交。,平面图的对偶图,平面图的对偶图,定义 设平面图G, 有p个顶点, q条边和f个面, 构造G的对偶图G*=如下：在G的每一个面fi中任取一个点vi*作为G*的顶点, V*= vi*| i=1,2,f .对G每一条边ek, 若ek在G的面fi与fj的公共边界上, 则作边ek*=(vi*,vj*), 且与ek相交; 若ek为G中的桥且在面fi的边界上, 则作环ek*=(vi*,vi*). E*= ek*| k=1,2, ,q .,平面图的对偶图（续）,例 黑色实线为原平面图, 红色虚线为其对偶图,平面图的对偶图(续),性质：G*是平面图，而且是平面嵌入.G*是连通图若边e为G中的环，则G*与e对应的边e*为桥; 若e为割边，则G*中与e对应的边e*为环.在多数情况下，G*含有重边.同构的平面图的对偶图不一定同构. 上面两个平面图是同构的, 但它们的对偶图不同构.,平面图与对偶图的阶数、边数与面数之间的关系:设G*是平面图G的对偶图，p*, q*, f*和p, q, f分别为G*和G的顶点数、边数和面数，则(1) p*= f(2) q*=q(3) f*=p-k+1, 其中k是G的连通分支数(4) 设G*的顶点vi*位于G的面fi中, 则d(vi*)=deg(fi),平面图的对偶图(续),定义9. 如果G的对偶图G*与G同构，则称G为自对偶图。 在下图(a)，(b)中，设实线边图是G，则虚线边图是G的对偶图G*。可以看出图G和它的对偶图G*是同构的。所以，下图(a)，(b)中的实线边图都是自对偶图。,例：,例：,谢谢!,