支配集、覆盖集、独立集、匹配与着色PPT课件

第18章支配集、覆盖集、独立集、匹配与着色,离散数学,中国地质大学本科生课程,.,2,本章说明,主要内容点着色地图着色与平面图的点着色边着色,.,3,本章所涉及到的图均指无向图。,.,4,18.4点着色18.5地图着色与平面图的点着色18.6边着色本章小结习题作业,.,5,定义18.7设G是具有互补结点子集V1和V2的二部图，其中V1=v1，v2，vr，V1对V2的匹配是G的一个子图，它由r条边v1，v1，v2，v2，vr，vr组成，其中，v1，v2，vr是V2中r个不同的元素。,否,存在V1对V2的匹配,18.3二部图中的匹配,.,6,例2某班级成立了三个运动队：篮球队、排球队和足球队。今有张、王、李、赵、陈5名同学，若已知张、王为篮球队员；张、李、赵为排球队员；李、赵、陈为足球队员，问能否从这5人中选出3名不兼职的队长？,在图中存在V1对V2的匹配，因此题目的要求可以满足。,.,7,定理18.6设G是具有互补结点子集V1和V2的二部图，若存在一整数t0，(1)对v1中的每个结点，至少有t条边与其相关联；(2)对v2中的每个结点，至多有t条边与其相关联。则G中存在v1对v2的匹配。,二部图存在匹配的充分条件：,.,8,18.4点着色,规定：点着色都是对无环无向图进行的。一、关于顶点着色的基本概念定义18.8（1）图G的一种着色对无环图G的每个顶点涂上一种颜色，使相邻顶点涂不同的颜色。（2）对G进行k着色（G是k-可着色的）能用k种颜色给G的顶点着色。（3）G的色数(G)=kG是k-可着色的，但不是(k1)-可着色的。,.,9,二、关于顶点着色的几个简单结果(G)=1当且仅当G为零图。(Kn)=n。奇圈或奇阶轮图的色数均为3，偶阶轮图的色数为4。设G中至少含有一条边，则(G)=2当且仅当G为二部图。,.,10,三、色数的上界定理18.7对于任意无向图G，均有(G)(G)+1。,n=1时，结论成立。设n=k(k1)时结论成立，则当n=k+1时，设v为G中任一个顶点，令G=G-v，则G的阶数为k，由假设可知(G)(G)+1(G)+1。当将G还原成G时，由于v至多与G中(G)个顶点相邻，而在G的点着色中，(G)个顶点至多用了(G)种颜色，于是在(G)+1种颜色中至少存在一种颜色给v涂色，使v与相邻顶点涂不同颜色。,证明,提示：对G的阶数n作归纳法。,.,11,例18.4求下面各图的色数。,定理18.8(布鲁克斯定理)若连通无向图G不是Kn(n3)，也不是奇数阶的圈，则(G)(G)。,因为(1)为二部图，由定理17.22可知，(G)=2。(2)为6阶轮图W6，由定理17.21可知，(G)=4。由定理17.24可知，(G)4，又因为(3)中有奇圈，于是(G)3，因而(G)为3或4，用3种颜色不可能给G4着色，于是只能是(G)=4。,解答,小节结束,.,12,18.5地图着色与平面图的点着色,一、地图与面着色1、地图与国家（1）地图连通无桥平面图的平面嵌入与所有的面。（2）国家地图的面。（3）两个国家相邻两个国家的边界至少有一条公共边。,有5个国家，1与2相邻，1与4相邻，2,3,4均与5相邻。,5,4,1,2,3,.,13,2、地图的面着色定义18.9（1）地图G的一种面着色对地图G的每个国家涂上一种颜色，使相邻国家涂不同的颜色。（2）G是k-面可着色的能用k种颜色给G的面着色，就称对G的面进行了k着色。（3）G的面色数*(G)=kG是k-面可着色的，但不是(k-1)-面可着色的，即最少用k种颜色给G的面着色。,研究地图的着色可以转化成对它的对偶图的点着色。,说明,.,14,二、地图的面着色转化成对偶图的点着色定理18.9地图G是k-面可着色的当且仅当它的对偶图G*是k-点可着色的。三、四色定理定理18.10任何平面图都是4-可着色的。四色猜想问题，提出来已经近150年了，但时至今日还没有得到彻底解决。,小节结束,.,15,18.6边着色,本节讨论的图是无环的无向图。一、对图G进行边着色定义18.10（1）对图G边的一种着色对图G的每条边涂上一种颜色，使相邻的边涂不同的颜色。（2）G是k-边可着色的能用k种颜色给G的边着色。（3）G的边色数(G)=k若G是k-边可着色的，但不是(k-1)-边可着色的，即最少用k种颜色给G的边着色。,.,16,二、关于边着色的一些定理定理18.11G为简单平面图，则(G)(G)(G)+1。,该定理是维津定理。定理说明，对简单图来说，它的边色数只能取它的(G)，或者是它的(G)+1。究竟哪些图的(G)是(G)，哪些是(G)+1，至今还是一个没有解决的问题。,例18.5设G为长度大于或等于2的偶圈，则(G)=(G)=2.设G为长度大于或等于3的奇圈，则(G)=(G)+1=3.,.,17,n=4时，由维津定理可知，结论正确。n=5时，由维津定理可知，结论正确。n6时，(Wn)=n-15，Wn中间顶点关联的n-1条边必须用n-1种颜色着色。而外圈Cn-1上的任何边都准确的与其余的4条边相邻，于是总可以找到n-1种色中的一种为它涂色，所以(Wn)n-1。又由维津定理可知，(Wn)n-1，所以(Wn)=n-1。,例18.6(Wn)=(Wn)=n1，其中n4。,定理18.12二部图的边色数等于最大度。,证明,.,18,例18.7当n(n1)为奇数时，(Kn)=n；当n为偶数时，(Kn)=n1。例17.5证明(W4)=(W4)=3，(W5)=(W5)=4。,由维津定理可知结论是正确的。,解答,.,19,例求下面所示各图的边色数。,小节结束,(1)中无奇长回路，所以它为二部图，由定理17.30可知=4。由维津定理可知，(2)中=4，又存在4种颜色的边着色，所以4，因而=4。,解答,.,20,本章主要内容,顶点的着色与点色数。关于点色数的一些定理。地图及其面着色、面色数。平面图的四色定理。边着色及边色数。关于边着色的一些定理。,.,21,本章学习要求,深刻理解点着色、边着色、点色数、边色数的