chap12图的着色.

第十二章图的着色1图的着色问题问题来源:地图的着色问题：用m种颜色为地图着色，使得地图上的每一个区域着一种颜色，且相邻区域颜色不同，最少需要多少种颜色？。一百多年前，英国格色里(Guthrie)提出了用四种颜色即可对地图着色的猜想，1976年美国数学家阿佩尔和黑肯用电子计算机证明了四色猜想是成立的，这就是著名的“四色定理”。图的着色问题问题处理：如果把每一个区域收缩为一个顶点，把相邻两个区域用一条边相连接，就可以把一个区域图抽象为一个平面图。区域用城市名表示，颜色用数字表示，则右图表示了不同区域的不同着色问题。顶点着色：用m种颜色为图的每个顶点着色，要求每个顶点着一种颜色，并使相邻两顶点之间有着不同的颜色。边着色：用m种颜色为图的每条边着色，要求每条边着一种颜色，并使相邻两条边有着不同的颜色。图着色的分类§12.1顶点着色定义12.1.1设G是标定图，S={1,,k},k1。•若存在V(G)到S的一个满射，则称是G的一个k着色，S称为色集；•如果对G中的任意邻接的两个顶点u,v，均有(u)≠(v)，则称是正常k着色，并称G是k可着色的。显然，p阶图总是p可着色的，若G是k(p)可着色的,则G一定是k+1可着色的.5K可着色的图例6213SG:V(G)→S,满射是正常3着色，G是3可着色的。v1v2v3v5v4K色图定义12.1.2图G的正常k着色中最小的k称为G的色数，记为(G)，即(G)=min{k|G存在正常k着色}。若(G)=k，则称G是k色图。显然，含环的图不存在正常着色，而多重边与一条边对正常着色是等价的。以后总设G为简单图。7问题：已知一个图G(p,q)，如何求色数(G)？几种特殊图的色数①G是零图p为偶数χ(G)=1②G是p阶完全图χ(G)=p③G是p个顶点的回路χ(G)=2p为奇数χ(G)=3几种特殊图的色数④G是非平凡树χ(G)=2⑤G是二分图χ(G)=2色数的估计而对于一般的图，要确定色数(G)是很困难的问题，目前只能根据图的最大独立集、最大（小）度等来估计(G)的上下界。独立集都是同色顶点回顾：独立集：图G中互不邻接的顶点子集，最大独立集的顶点数α(G)。一个独立集中的顶点可以着同一种颜色对于p阶图G，着色方案一：•将顶点集合V(G)划分成若干个互不相交的独立集；•每一个独立集分别着一种颜色。因为最少有p/α(G)个独立集，所以色素χ(G)≥p/α(G)独立集都是同色顶点回顾：独立集：图G中互不邻接的顶点子集，最大独立集的顶点数α(G)。一个独立集中的顶点可以着同一种颜色对于p阶图G，着色方案二：•将最大独立集着同一种颜色；•其余每个顶点分别着另一种颜色。此为颜色最多的着色方案，所以色素χ(G)≤p-α(G)+1色数与独立数定理12.1.1对任何p阶图G,有p/(G)(G)p–(G)+1，其中，(G)是G的独立数。13以上定理说明，若已知(G)的下上界就可确定(G)的上下界，但(G)的上下界一般也是难以确定的。下面给出新的概念来导出(G)的上下界。临界点与临界图定义12.1.3设G是图，v∈V(G)，若(G–v)(G)，则称v是临界点。若G的每个点都是临界点，则称G是临界图。141432临界图1233非临界图临界图的性质性质1：图G中的顶点v是临界点，当且仅当(G–v)=(G)–1。性质2：若顶点v是图G的一个临界点，则有d(v)≥(G)-1.定理12.1.2：若G是临界图，则有(G)≥(G)-1定理12.1.3：任何p阶图G都含有一个临界的导出子图H，使得(H)=(G)。15得到了临界图的上述性质后，下面我们讨论任意图G，其(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。16临界点的度不小于色数减一性质2：若顶点v是图G的临界点，则有d(v)≥(G)-1证明；由性质1，G–v有正常((G)–1)着色。17……v(G)–1d(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。性质2之逆不真。(G)–1临界图最小度不小于色数减一定理12.1.2若G是一个临界图，则(v)≥(G)–1证明：由性质2知，任意临界点v，都有d(v)≥(G)–1。而临界图G中每个顶点都是临界点，即所有顶点的度都不小于色数减一，所以(G)≥(G)–1。18图有同色的临界导出子图定理12.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的临界的导出子图。•由归纳法知，定理成立。19K色图中顶点的度推论12.1.1任何k色图中至少有k个顶点的度不小于k–1。证明：设(G)=k，H是G的一临界子图，则有(H)=(G)=k。由定理12.1.2可知，(H)(H)–1，因为H是k色的，所以H中至少有k个点，又因为对任意的v∈V(H),有dG(v)dH(v)(H)k–1。故结论成立。20色数的另一个上界定理12.1.4对任何图G，有(G)≤(G)+1。（(G)表示图G的最大度）证明：反设(G)(G)+1，即(G)≥(G)+2。令(G)=k，则(G)≤k-2。由推论12.1.1，G至少有k个顶点的度不小于k–1，即大于或等于k-1，即d(v)≥k-1。又因k＞0，所以与(G)定义矛盾。结论成立。注意此定理与定理12.1.2的区别。定理12.1.2若G是一个临界图，则(G)≤(G)+121Brooks定理定理12.1.5若连通图G既不是奇回路，也不是完全图，则(G)(G).22此定理说明只有奇回路或完全图这两类图的色数才是(G)+1。例如，对Petersen图应用Brooks定理，可得：(G)(G)=3.色数的一个下界定理12.1.6对图G(p,q)，有(G)2q/p2+1。证明：略。23将此结论用于Petersen图,得(G)𝟐×𝟏𝟓𝟏𝟎𝟐+1=𝟑𝟎𝟏𝟎𝟎+1=2.又由Brooks定理(G)≤3，而显然Petersen图不是2-可着色的，所以(G)=3。小结关于图G(p,q)的色数(G)问题，我们有如下结论。①p/(G)(G)p–(G)+1，(G)为点独立数；②奇回路和完全图的色数是(G)+1；③2q/p2+1(G)(G)，(G)为最大度；④若G中含有奇回路，则(G)≥3。练一练求下列各图的色数(G)。1.G1是二分图，所以(G)=2；2.G2外圈为奇回路，中间点与回路上所有点邻接，所以(G)=4；3.G3中含有奇回路，最大度为4，所以3(G)4，而显然不是3可着色的，所以(G)=4点着色的应用课程安排问题某大学数学系要为这个夏季安排课程表。所要开设的课程为：图论(GT),统计学(S),线性代数(LA),高等微积分(AC),几何学(G)和近世代数(MA)。现有10名学生(如下所示)需要选修这些课程。根据这些信息，确定开设这些课程所需要的最少时间段数，使得学生选课不会发生冲突。(学生用Ai表示）A1:LA,S;A2:MA,LA,G;A3:MA,G,LA;A4:G,LA,AC;A5:AC,LA,S;A6:G,AC;A7:GT,MA,LA;A8:LA,GT,S;A9:AC,S,LA;A10:GT,S。课程安排问题第一步：建图。把每门课程做为图G的顶点，两顶点连线当且仅当有某个学生同时选了这两门课程。GTMAGACLAS选课状态图第二步：分析。如果我们用同一颜色给同一时段的课程顶点染色，那么，问题转化为在状态图中求点色数问题。课程安排问题第三步：求解。GTMAGACLAS选课状态图仔细观察，图中含有奇回路，所以(G)≥3又顶点LA与回路上的每个顶点均邻接，所以(G)≥4通过具体着色，用4种颜色可以得到该图的一种正常点着色，则(G)=4结论：这六门课程至少需要排4个时间段才不会使选课学生冲突。§12.2边着色排课表问题设有m位教师，n个班级，其中教师xi要给班级yj上pij节课。求如何在最少节次排完所有课。建模：令X=｛x1,x2,…,xm｝,Y=｛y1,y2,…,yn｝,xi与yj间连pij条边，得二分图G=X,Y。分析：问题转化为如何在G中将边集E划分为互不相交的p个匹配，且使得p最小。求解：如果每个匹配中的边用同一种颜色染色，不同匹配中的边用不同颜色染色，则问题转化为在G中给每条边染色，相邻边染不同色，至少需要的颜色数。这就需要我们研究所谓的边着色问题。边着色基本概念30定义12.2.1设G是图，S={1,,k},k1。•若存在E(G)到S的一个满射，则称是G的一个k边着色，S称为边色集；•如果对G中的任意邻接的两条边e1、e2,均有(e1)≠(e2)，则称是正常k边着色，并称G是k边可着色的。显然,有q条边的图是q边可着色的。若G是k(k＜q)边可着色的，则G也是k+1边可着色的。与顶点v关联的边上所着的颜色i又称为颜色i在v上出现。边色数定义12.1.2图G的正常k边着色中，最小的k称为G的边色数，记为(G)。易知，(G)(G)。31(G)=3’(G)=3ve(e)=i(G)=2’(G)=3问题：’(G)的上界呢？通路上可以交叉着色(1)引理12.2.1设连通图G不是长度为奇数的回路，于是，G有一个2边着色（不要求正常着色），使得这两种颜色在度至少为2的每个顶点上都出现。32证明：(1)若G是通路，则引理成立。偶通路：奇通路：通路上可以交叉着色(2)引理12.2.1设连通图G不是长度为奇数的回路，于是，G有一个2边着色（不要求正常着色），使得这两种颜色在度至少为2的每个顶点上都出现。33证明：(2)若G是一个长度为偶数的回路，则引理显然成立。奇回路：偶回路：通路上可以交叉着色(3)引理12.2.1设连通图G不是长度为奇数的回路，于是，G有一个2边着色（不要求正常着色），使得这两种颜色在度至少为2的每个顶点上都出现。34证明：(3)若G不是通路也不是偶回路，wG1中无奇点，必为E图G1中含E闭链用两种颜色给该E闭链依次着色增加一顶点w，使w与G中所有奇点邻接，得到一个E图G1。顶点上出现的颜色越多越美丽定义12.2.3设是图G的k边着色。令C(v)表示在下顶点v上出现的不同颜色的数目，对于G的两个k边着色和，称优于，如果C(v)C(v)v∈V(G)v∈V(G)若没有优于的k边着色，则称是最优k边着色。注意这里没有要求是图G的正常k边着色。显然C(v)≤dG(v)（即在顶点v上最多出现d(v)中颜色）对任意v∈V(G)，都有：C(v)=dG(v)当且仅当是正常k边着色。35定义12.2.3的例如下图G的两个2边着色：36C(v)=2+2+2+2=8C(v)=1+2+1+2=6故优于，易知，是最优2边着色。缺