第九章-图的着色

第九章色数图的点着色数着色数的基本性质Brooks定理图的边着色数地图着色问题问题来源图的着色问题是由地图的着色问题引申而来的：用m种颜色为地图着色，使得地图上的每一个区域着一种颜色，且相邻区域颜色不同。问题处理：如果把每一个区域收缩为一个顶点，把相邻两个区域用一条边相连接，就可以把一个区域图抽象为一个平面图。问题来源例如，图9-1（a）所示的区域图可抽象为9-1（b）所表示的平面图。19世纪50年代，英国学者提出了任何地图都可以4种颜色来着色的4色猜想问题。过了100多年，这个问题才由美国学者在计算机上予以证明，这就是著名的四色定理。例如，在图9-1中，区域用城市名表示，颜色用数字表示，则图中表示了不同区域的不同着色问题。区域和点的对应5四色问题(FourColorProblem)1852,FrancisGuthrie,注意到英格兰地图可以用4种颜色染色,使得相邻区域(有一段公共边界,不只是有一个公共点)有不同颜色;他问其弟Frederick是否任意地图都有此性质?FrederickGuthrieDeMorganHamilton.1878,Cayley,提交伦敦数学会.FrancisGuthrie的猜想给地图的每个区域着色，保持任何有公共边界的区域使用不同颜色，只要四种颜色就够了。很容易证明，三种颜色是不够的-Guthrie,deMorgan可以证明：任何地图不会有这样的构型：5个区域，每个均与其它4个相邻。误认为这蕴涵四色猜想导致许多错误证明上图中没有4个区域两两都相邻，但三色不够。7四色问题(FourColorProblem)8四色问题(FourColorProblem)1879,Kempe,第一次“证明”1880,Tait,另一个“证明”1890,Heawood发现Kempe证明的错误1891,Petersen发现Tait证明的漏洞(Tait猜想)1946,Tutte发现Tait证明的错误(Tait猜想反例)9四色问题(FourColorProblem)1913,Birkhoff,一个大贡献1922,Franklin,证明不超过22个区域的地图四色猜想成立1950,不超过35个区域1960,不超过39个区域其他人取得其他形式进展:1974,52区域10四色问题(FourColorProblem)1936-50,Heesch,最终解决问题的两个要素:10000个情形,100年约化(reducibility),放电(discharging).1972-76,Appel,Haken,1482个情形,IBM360,1200小时,论文139页+400页程序,conjectureagnogramstheorem11四色问题(FourColorProblem)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。x1x2y1x3x4x5y2y3y4y5临界图定义：若图G的着色数是k,但vVG,(G-v)k,则称G是k-临界图。临界点与临界图•定义9.1.3：设G是图，v∈V(G)，若(G–v)(G)，则称v是临界点。若G的每个点都是临界点，则称G是临界图。G是k-临界图即：G的着色数是k,但G的任何真子图的着色数均小于k。任何k-色图必含有k-临界子图。如果G是k-临界图，G一定是连通图。注意：G一定有着色数是k的连通分支。黄绿对换,可空出黄色中心点的5个邻点也必须用3色一个4-临界图的例子外围的奇回路必须用3色Grötzwch图临界图的性质:•1、图G中的顶点v是临界点，当且仅当(G–v)=(G)–1。•2、若顶点v是图G的一个临界点，则有d(v)(G)–1.•3、若G是临界图，则有(G)(G)–1•4、任何p阶图G都含有一个临界的导出子图H，使得(H)=(G)。临界点使色数减一•性质1：图G的顶点v是临界点，当且仅当(G–v)=(G)–1。•证明：若(G–v)=(G)–1,则(G–v)(G)，即v是临界点。•反之，若v是临界点，则(G–v)(G)，即(G–v)(G)–1。如果(G–v)(G)–1，则有(G–v)(G)–2，于是G–v有一个正常((G)–2)着色，从而G也就有一个正常((G)–1)着色。此与(G)的定义相矛盾。故(G–v)=(G)–1。临界点的度不小于色数减一•性质2：若顶点v是图G的临界点，则有d(v)≥(G)–1。•证明；由性质1，G–v有正常((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时显然成立。•归纳步骤：设对p–1个顶点的图结论成立。G是p阶图，若任何v∈V(G)，(G–v)=(G)–1,则G本身是一个临界图；否则，有u∈V(G)，使(G–u)=(G)。由归纳假设，G–u含临界的导出子图H,且(H)=(G–u)=(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个点，又因为对任意的v∈V(H),有dG(v)dH(v)(H)k–1。故结论成立。•定理9.1.4：对任何图G，有(G)≤(G)+1，这里(G)表示图G的最大度。•证明：假设(G)≥(G)+2。令(G)=k。由推论9.1.1，G至少有k个顶点的度不小于k–1，即大于等于(G)+1。因(G)＞0，所以G中有度大于(G)的顶点，此与(G)定义矛盾。结论成立。•注意此定理与定理9.1.2的区别。(定理9.1.2：若G是一个临界图，则(G)≥(G)–1。)Brooks定理若连通图G不是完全图Kn(n3),也不是奇圈，则：(G)(G)•对Petersen图应用上述结果，得到χ(G)≤30.810.60.40.20xt00.511.5210.500.51nG：uv(u，v着一样的颜色时)表示u，v在G中不邻接，将这两个顶点对粘uvfkhuvhkfuvhkf0.810.60.40.20xt00.511.5210.500.51nG+uv(u，v着不一样的颜色时)表示u，v在G中不邻接，将这两个顶点连接uvfkh0.810.60.40.20xt00.511.5210.500.51nG：uv表示u，v在G中不邻接，将这两个顶点对粘uvfkhuvhkfuvhkf定理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)证明：假设存在vV,满足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中最小顶点度数。证明：vVG,与v不相邻的顶点最多n--1个，如果给G正常着色，同颜色的顶点最多n-个，(n-)(G)n求着色数的例子上左：二部图（图中无奇回路）上右：轮下左：有奇回路，=3，=3下右：有奇回路，=4，但不可能是3考试时间表编排问题的解建立图模型每一个顶点对应为一门考试，任何两点相邻当且仅当至少有一个学生必须参加该两点所对应的两门考试。(因此，该两门考试必须安排在不同的时间)问题的解