《图论》课件第十八章.ppt

1、1第十八章支配集、覆盖集、第十八章支配集、覆盖集、独立集、匹配与着色独立集、匹配与着色主要内容主要内容l 支配集、点覆盖集与点独立集支配集、点覆盖集与点独立集l 边覆盖与匹配边覆盖与匹配l 二部图中的匹配二部图中的匹配l 点着色点着色l 地图着色与平面图的点着色地图着色与平面图的点着色l 边着色边着色218.1 支配支配集、点覆盖集集、点覆盖集与点独立集与点独立集支配集与支配数支配集与支配数定义定义18.1 设设G=，V*V.(1)V*为为支配集支配集 vi V V*,vj V*，使得，使得(vi,vj)E(2)V*为为极小支配集极小支配集V*的真子集不是支配集的真子集不是支配集(3)最小支配

2、集最小支配集元素最少的支配集元素最少的支配集(4)支配数支配数 0(G)最小支配集中的元素个数最小支配集中的元素个数3极小与最小支配集之间的关系极小与最小支配集之间的关系最小支配集为极小支配集，但反之不真最小支配集为极小支配集，但反之不真.另外，极小支配集与最小支配集都可能不惟一另外，极小支配集与最小支配集都可能不惟一.又易知完全图、轮图、星形图的支配数均是又易知完全图、轮图、星形图的支配数均是1.图中，图中，(1),(2),(3)(彼得松图彼得松图)的支配数分别为的支配数分别为1，2，3.请各找出一个最小支配集请各找出一个最小支配集.(1)(2)(3)4点独立集与点独立数点独立集与点独立数定

3、义定义18.2 设设G=，V*V.(1)点独立集点独立集V*V*中顶点彼此不相邻中顶点彼此不相邻(2)V*为为极大点独立集极大点独立集V*中再加入任何顶点就不是点独中再加入任何顶点就不是点独立集立集(3)最大点独立集最大点独立集元素最多的点独立集元素最多的点独立集(4)点独立数点独立数最大点独立集中的元素个数，记为最大点独立集中的元素个数，记为 0 在图中，点独立数依次为在图中，点独立数依次为2,2,3.(1)(2)(3)5极大独立集与极小支配集极大独立集与极小支配集定理定理18.1 设设G=中无孤立点，则中无孤立点，则G的极大点独立集都是的极大点独立集都是极小支配集极小支配集.证明线索：证明

4、线索：(1)设设V*为为G的极大点独立集，证明它也是支配集的极大点独立集，证明它也是支配集.v V V*，必，必 vV*，使，使(v,v)E，否则，否则 v0 V V*不不与与V*中任何顶点相邻，则中任何顶点相邻，则V*v0仍为点独立集，这与仍为点独立集，这与V*是极大点独立集矛盾是极大点独立集矛盾.(2)证证V*是极小支配集是极小支配集.只需证只需证V*的真子集不是支配集的真子集不是支配集.特别注意，特别注意，定理定理18.1其逆不真其逆不真.6点覆盖集与点覆盖数点覆盖集与点覆盖数定义定义18.3 设设G=,V*V.(1)V*是是点覆盖集点覆盖集 e E，v V*，使，使e与与v关联关联(2

5、)V*是是极小点覆盖集极小点覆盖集V*的任何真子集都不是点覆盖集的任何真子集都不是点覆盖集(3)最小点覆盖集最小点覆盖集(或最小点覆盖或最小点覆盖)顶点数最少的点覆盖集顶点数最少的点覆盖集(4)点覆盖数点覆盖数 0(G)最小点覆盖的元素个数最小点覆盖的元素个数图中，点覆盖数依次为图中，点覆盖数依次为3，4，7.7点覆盖集与点独立集的关系点覆盖集与点独立集的关系定理定理18.2 设设G=无孤立点，无孤立点，V*V，则，则V*是点覆盖当且是点覆盖当且仅当为点独立集仅当为点独立集证证 必要性必要性.若若 vi,vj 相邻，即相邻，即(vi,vj)E，则，则V*中顶点不能覆中顶点不能覆盖盖(vi,vj

6、)，这是矛盾的，这是矛盾的.充分性充分性.由于是点独立集，因而由于是点独立集，因而 e E，e的两个端点至少一的两个端点至少一个在个在V*中中.推论推论 设设G为为n阶无孤立顶点图，则阶无孤立顶点图，则V*是极小是极小(最小最小)点覆盖当点覆盖当且仅当是极大（最大）点独立集，从而有且仅当是极大（最大）点独立集，从而有 0+0=n8 18.2 边覆盖集与匹配边覆盖集与匹配边覆盖集与边覆盖数边覆盖集与边覆盖数定义定义18.4 设设G=，E*E，(1)E*为为边覆盖集边覆盖集 v V，e E，使得，使得v与与e关联关联(2)E*为为极小边覆盖极小边覆盖E*的真子集不是边覆盖的真子集不是边覆盖(3)最

7、小边覆盖最小边覆盖边数最少的边覆盖边数最少的边覆盖(4)边覆盖数边覆盖数 1最小边覆盖中元素个数最小边覆盖中元素个数 图中各图的边覆盖数依次为图中各图的边覆盖数依次为3,4,5.请各找出一个最小边覆盖请各找出一个最小边覆盖.9匹配匹配(边独立集边独立集)与匹配数与匹配数(边独立数边独立数)定义定义18.5 设设G=,E*E，(1)匹配匹配(边独立集边独立集)E*E*中各边均不相邻中各边均不相邻(2)极大匹配极大匹配E*E*中不能再加其他边了中不能再加其他边了(3)最大匹配最大匹配边数最多的匹配边数最多的匹配(4)匹配数匹配数最大匹配中的边数，记为最大匹配中的边数，记为 1 上图中各图的匹配数依

8、次为上图中各图的匹配数依次为3,3,4.10 关于匹配中的其他概念关于匹配中的其他概念定义定义18.6 设设M为为G中一个匹配中一个匹配.(1)vi 与与vj 被被M匹配匹配(vi,vj)M(2)v为为M饱和点饱和点有有M中边与中边与v关联关联(3)v为为M非饱和点非饱和点无无M中边与中边与v关联关联(4)M为为完美匹配完美匹配G中无中无M非饱和点非饱和点(5)M的的交错路径交错路径从从M与与E M中交替取边构成的中交替取边构成的G中路径中路径(6)M的的可增广交错路径可增广交错路径起、终点都是起、终点都是M非饱和点的交错非饱和点的交错路径路径(7)M的的交错圈交错圈由由M与与E M中的边交替

9、出现构成的中的边交替出现构成的G中圈中圈上图中，只有第一个图存在完美匹配上图中，只有第一个图存在完美匹配11可增广路径及交错圈可增广路径及交错圈设红色边在匹配设红色边在匹配M中，绿色边不在中，绿色边不在M中，则图中，则图(1)中的两条路中的两条路径均为可增广的交错路径；径均为可增广的交错路径；(2)中的全不是可增广的交错路中的全不是可增广的交错路径；径；(3)中是一个交错圈中是一个交错圈.不难看出，可增广交错路径中，不在不难看出，可增广交错路径中，不在M中的边比在中的边比在M中的边中的边多一条多一条.交错圈一定为偶圈交错圈一定为偶圈.(1)(2)(3)12最大匹配与最小边覆盖之间关系最大匹配与

10、最小边覆盖之间关系定理定理18.3 设设n阶图阶图G中无孤立顶点中无孤立顶点.(1)设设M为为G中一个最大匹配，对于中一个最大匹配，对于G中每个中每个M非饱和点均取非饱和点均取一条与其关联的边，组成边集一条与其关联的边，组成边集N，则，则W=M N为为G中最小中最小边覆盖边覆盖.(2)设设W1为为G中一个最小边覆盖；若中一个最小边覆盖；若W1中存在相邻的边就移中存在相邻的边就移去其中的一条，设移去的边集为去其中的一条，设移去的边集为N1，则，则M1=W1 N1为为G中中一个最大匹配一个最大匹配.(3)G中边覆盖数中边覆盖数 1与匹配数与匹配数 1满足满足 1+1=n.证明见教材证明见教材.13

11、推论推论推论推论 设设G是是n阶无孤立顶点的图阶无孤立顶点的图.M为为G中的匹配，中的匹配，W是是G中中的边覆盖，则的边覆盖，则|M|W|，等号成立时，等号成立时，M为为G中完美匹配，中完美匹配，W为为G中最小边覆盖中最小边覆盖.图中，红边为匹配图中，红边为匹配M中的边中的边.(1)中匹配是最大匹配中匹配是最大匹配.(2)中红中红边与绿边组成最小边覆盖边与绿边组成最小边覆盖W.反之，由反之，由(2)的最小边覆盖的最小边覆盖W产生产生(1)中的最大匹配中的最大匹配M.(1)(2)14最大匹配判别定理最大匹配判别定理证明线索：证明线索：必要性必要性.若含可增广交错路径，可生成比若含可增广交错路径，

12、可生成比M更大的匹配更大的匹配.充分性充分性.设设M和和M1分别为不含可增广路径的匹配和最大匹分别为不含可增广路径的匹配和最大匹配，只要证明配，只要证明|M|=|M1|即可即可.由必要性知，由必要性知，M1也不含可增广也不含可增广交错路径交错路径.设设H=GM1 M，若，若H=，M=M1，结论为真，结论为真.否否则则H.此时，此时，H中的交错圈中的交错圈(若存在若存在)，其上，其上M与与M1的边的边数相等，且所有交错路径上，数相等，且所有交错路径上，M与与M1中的边数也相等（因中的边数也相等（因为为M与与M1均无可增广路径）均无可增广路径）.定理定理18.4 M为为G中最大匹配当且仅当中最大匹

13、配当且仅当G中不含中不含M的可增广交的可增广交错路径错路径.1518.3 二部图中的匹配二部图中的匹配定义定义18.7 设设G=为二部图，为二部图，|V1|V2|，M是是G中中最大匹配，若最大匹配，若V1中顶点全是中顶点全是M饱和点，则称饱和点，则称M为为G中中完备匹完备匹配配.|V1|=|V2|时完备匹配变成时完备匹配变成完美匹配完美匹配.图中，红边组成各图的一个匹配，图中，红边组成各图的一个匹配，(1)中为完备匹配，中为完备匹配，(2)中匹中匹配不是完备的，配不是完备的，(2)中无完备匹配，中无完备匹配，(3中匹配是完备的，也是完中匹配是完备的，也是完美的美的.(1)(2)(3)16Hal

14、l定理定理定理定理18.5 （Hall定理定理）设二部图）设二部图G=中，中，|V1|V2|.G中存在从中存在从V1到到V2的完备匹配当且仅当的完备匹配当且仅当V1中任意中任意k(k=1,2,|V1|)个顶点至少与个顶点至少与V2中的中的k个顶点相邻个顶点相邻.本定理中的条件常称为本定理中的条件常称为“相异性条件相异性条件”.由由Hall定理立刻可知，上图中定理立刻可知，上图中(2)为什么没有完备匹配为什么没有完备匹配.定理定理18.6 设二部图设二部图G=中，中，V1中每个顶点至少关联中每个顶点至少关联t(t 1)条边，而条边，而V2中每个顶点至多关联中每个顶点至多关联 t 条边，则条边，则

15、G 中存在中存在V1到到V2的完备匹配的完备匹配.证明要点：满足相异性条件证明要点：满足相异性条件.定理定理18.6中的条件称为中的条件称为 t（t 1）条件条件.17一个应用实例一个应用实例某课题组要从某课题组要从a,b,c,d,e 5人中派人中派3人分别到上海、广州、香人分别到上海、广州、香港去开会港去开会.已知已知a只想去上海，只想去上海，b只想去广州，只想去广州，c,d,e都表示想都表示想去广州或香港去广州或香港.问该课题组在满足个人要求的条件下，共有问该课题组在满足个人要求的条件下，共有几种派遣方案？几种派遣方案？解解 用二部图中的匹配理论解本题方便用二部图中的匹配理论解本题方便.令

16、令G=，其中，其中V1=s,g,x，s,g,x分别表示上海、广分别表示上海、广州和香港州和香港.V2=a,b,c,d,e,E=(u,v)|u V1,v V2,v想去想去u.G如图所示如图所示.G满足相异性条件，因而可满足相异性条件，因而可派遣，共有派遣，共有9种派遣方案种派遣方案(请请给出这给出这9种方案种方案).1818.4 点着色点着色定义定义17.9 (1)图图G的一种的一种点着色点着色给图给图G的每个顶点涂上一种颜色，的每个顶点涂上一种颜色，使相邻顶点具有不同颜色使相邻顶点具有不同颜色(2)对对G进行进行k着色着色（G是是k-可着色的）可着色的）能用能用k种颜色给种颜色给G的顶点着色的

17、顶点着色(3)G的的色数色数(G)=kG是是k-可着色的，但不是可着色的，但不是(k 1)-可着色可着色的的.19关于顶点着色的几个简单结果关于顶点着色的几个简单结果定理定理17.19 (G)=1当且仅当当且仅当G为零图为零图定理定理17.20 (Kn)=n 定理定理17.21 若若G为奇圈或奇阶轮图，则为奇圈或奇阶轮图，则(G)=3，若，若G为偶阶轮为偶阶轮图，则图，则(G)=4.定理定理17.22 若若G的边集非空，则的边集非空，则(G)=2当且仅当当且仅当G为二部图为二部图.上述各图中，色数分别为上述各图中，色数分别为3，4，3，5，为什么？为什么？20三、色数的上界色数的上界定理定理1

18、7.23 对于任意无向图对于任意无向图G，均有，均有 (G)(G)+1证明线索：对证明线索：对G的阶数的阶数n做归纳做归纳.定理定理17.24 若连通无向图若连通无向图G不是不是Kn,（n 3），也不是奇数阶），也不是奇数阶的圈，则的圈，则 (G)(G)定理定理17.24称为布鲁克斯定理称为布鲁克斯定理.2118.5 地图着色与平面图的点着色地图着色与平面图的点着色定义定义17.10 (1)地图地图连通无桥平面图（嵌入）与所有的面连通无桥平面图（嵌入）与所有的面(2)国家国家地图的面地图的面(3)两个国家两个国家相邻相邻它们的边界至少有一条公共边它们的边界至少有一条公共边在上图的地图中，有在上

19、图的地图中，有5个国家，其中个国家，其中1与与2相邻，相邻，1与与4相邻，相邻，2,3,4均与均与5相邻相邻.22地图的面着色地图的面着色定义定义17.11(1)地图地图G的的面着色面着色对对G的每个国家涂上一种颜色，相邻的每个国家涂上一种颜色，相邻国家涂不同颜色国家涂不同颜色(2)G是是k-面可着色的面可着色的能用能用k种颜色给种颜色给G的面着色的面着色(3)G的的面色数面色数*(G)=k最少用最少用k种颜色给种颜色给G的面着色的面着色.地图的面着色转化成对偶图的点着色地图的面着色转化成对偶图的点着色定理定理17.25 地图地图G是是k-面可着色的当且仅当它的对偶图面可着色的当且仅当它的对偶

20、图G*是是k-点可着色的点可着色的.证明简单证明简单五色定理五色定理定理定理17.26 任何平面图都是任何平面图都是5-可着色的可着色的剩下的大问题：四色猜想是否为真剩下的大问题：四色猜想是否为真23 18.6 边着色边着色(无环无向图无环无向图)定义定义17.12(1)对对G的边着色的边着色每条边着一种颜色，相邻的边不同色每条边着一种颜色，相邻的边不同色(2)G是是k-边可着色的边可着色的能用能用k种颜色给种颜色给G的边着色的边着色(3)G的边色数的边色数(G)最少用最少用k种颜色给种颜色给G的边着色的边着色定理定理17.27 (Vizing定理定理)G为简单平面图，则为简单平面图，则 (G

21、)(G)(G)+1.定理定理17.28 偶圈边色数为偶圈边色数为2，奇圈边色数为，奇圈边色数为3.定理定理17.29 (Wn)=n 1,n 4.定理定理17.30 二部图的边色数等于最大度二部图的边色数等于最大度.定理定理17.31 n为奇数（为奇数（n 1）时，）时，(Kn)=n；n为偶数时，为偶数时，(Kn)=n 1.24第十八章第十八章 习题课习题课主要内容主要内容l(点点)支配支配集、点覆盖集、点独立集集、点覆盖集、点独立集l 边覆盖集、匹配（边独立集）边覆盖集、匹配（边独立集）l 二部图中的完备匹配二部图中的完备匹配l 图的点着色、边着色、地图着色图的点着色、边着色、地图着色基本要求

22、基本要求l 深刻理解与支配集、点覆盖集、边覆盖集、点独立集、边深刻理解与支配集、点覆盖集、边覆盖集、点独立集、边独立集独立集(匹配匹配)、点着色、边着色、面着色、色数等、点着色、边着色、面着色、色数等概念概念l 会求阶数会求阶数 n 较小或特殊图的较小或特殊图的 0,0,0,1,1l 会用二部图中匹配的理论解简单问题会用二部图中匹配的理论解简单问题l 理解并记住地图面着色与它的对偶图点着色之间的关系理解并记住地图面着色与它的对偶图点着色之间的关系l 会用点色数及边色数解决一些实际问题会用点色数及边色数解决一些实际问题.25练习练习1(1)G中有不是最小支配集的极小支配集吗？求支配数中有不是最小

23、支配集的极小支配集吗？求支配数 0(2)G中有不是最小点覆盖集的极小点覆盖集吗？求点覆盖数中有不是最小点覆盖集的极小点覆盖集吗？求点覆盖数 0(3)G中有不是最大点独立集的极大点独立集吗？求中有不是最大点独立集的极大点独立集吗？求 0.(4)G中有完美匹配吗？为什么？求匹配数中有完美匹配吗？为什么？求匹配数 1(5)求边覆盖数求边覆盖数 1 1无向图无向图G如下所示如下所示.26解答解答(1)共有共有8个极小支配集：个极小支配集：v1,v2,v1,v3,v1,v4,v1,v5,v2,v3,v3,v4,v3,v5,v2,v4,v5.只有最后一个不是最小的，只有最后一个不是最小的，0=2(2)共有

24、共有2个极小点覆盖集：个极小点覆盖集：v1,v3,v2,v4,v5，前者是最小，前者是最小 的，的，0=2(3)共有共有2个极大点独立集：个极大点独立集：v1,v3,v2,v4,v5，后者是最大，后者是最大 的，的，0=3(4)G不可能有完美匹配，因为它的阶数不可能有完美匹配，因为它的阶数n=5(奇数奇数)，1=2 (G的最大匹配为的最大匹配为2元集元集)(5)由定理由定理18.3立刻可知立刻可知 1=327练习练习22.彼得松图如下图所示：彼得松图如下图所示：在图上给出一个最大点独立集和一个最大匹配，从而求出在图上给出一个最大点独立集和一个最大匹配，从而求出 0,1,以及以及 0和和 1.2

25、8解 由观察法在上图由观察法在上图(1)中给出一个点独立集，在中给出一个点独立集，在(2)中给出了一中给出了一个最大匹配个最大匹配.从而得出从而得出 0=4，1=5.由定理由定理18.2推论知推论知 0=6，由定理，由定理18.3可知可知 1=5.解答解答29练习练习3解解 本题应用定理本题应用定理8.2的推论（的推论（0+0=n）与定理）与定理8.3中的中的(3)（1+1=n）较为方便）较为方便.(1)由于在由于在Kn中，任何两个顶点均相邻，因而中，任何两个顶点均相邻，因而 0=1，故有，故有 0=n 1（0+0=n）.(2)n为偶数时，为偶数时，Kn中存在完美匹配，所以中存在完美匹配，所以

26、 1=，故，故当当n为奇数时，为奇数时，Kn中不可能有完美匹配，中不可能有完美匹配，Kn v（从（从Kn中任意删中任意删除顶点除顶点v）为）为Kn 1(n 1为偶数为偶数)，于是，于是Kn 1中存在完美匹配，中存在完美匹配，但但Kn 1中的完美匹配为中的完美匹配为Kn中的最大匹配，故中的最大匹配，故Kn中的中的 ，于，于是是 3求无向完全图求无向完全图Kn（n 3）中的）中的 0,1,0,1.2n)(22111nnnn211n211n)(21111nn30练习练习4 由二部图的定义及题中参数的定义，不难看出由二部图的定义及题中参数的定义，不难看出 0=1=r，1=0=s.4求完全二部图求完全二

27、部图Kr,s（1 r s）的）的 0,1,0,1.31练习练习55.求图的点色数求图的点色数 ,边色数边色数 ,以及面色数以及面色数 *.解解(1)因为因为G中含奇圈，所以中含奇圈，所以3，由布鲁克斯定理知由布鲁克斯定理知=4,又容易证明不能用又容易证明不能用3种颜色涂色：种颜色涂色：由于由于a,b,c 彼此相邻，因而至少用彼此相邻，因而至少用3种颜色涂色，设用颜色种颜色涂色，设用颜色,分分别给别给a,b,c 涂色涂色.此时最少还用这此时最少还用这三种颜色给三种颜色给d,e,f 涂色，而且涂色，而且d,e,f也只能用颜色也只能用颜色 ,和和，这样，这样g只能只能用另一种颜色，比如用另一种颜色，

28、比如 涂色，所涂色，所以以 =4.32(2)由维津（由维津（Vizing）定理可知）定理可知=4或或5，但可用，但可用4种颜色给边种颜色给边涂色，如图所示涂色，如图所示.练习练习533图20 图19(3)易知图的对偶图为图易知图的对偶图为图(1)所示，容易证明它的点色数为所示，容易证明它的点色数为4，所，所以图以图17的面色数的面色数*=4，见图，见图(2)所示所示.(1)(2)练习练习5346.设设G为为3-正则的哈密顿图，证明正则的哈密顿图，证明(G)=3.练习练习6证证 用维津定理及握手定理即可证用维津定理及握手定理即可证.由维津定理知由维津定理知 3=(G)(G)(G)+1=4.下面只

29、需证可用下面只需证可用3种颜色给种颜色给G的边着色的边着色.设设C为为G中的哈密顿回路，则中的哈密顿回路，则C为偶圈为偶圈(3n=2m)，所以用两种，所以用两种颜色可给颜色可给C的边着色的边着色.G中不在中不在C上的边彼此不邻上的边彼此不邻(为什么？为什么？)，因而用第因而用第3种颜色给它们着色即可种颜色给它们着色即可.35练习练习77.某校计算机系三年级学生在本学期共选某校计算机系三年级学生在本学期共选6门选修课门选修课Ci,i=1,2,6.设设S(Ci)为选为选Ci课的学生集课的学生集.已知已知 S(Ci)S(C6),i=1,2,5，S(Ci)S(Ci+1),i=1,2,3,4，S(C5)S(C1).问这问这6门课至少几天能考完？门课至少几天能考完？36解 解答解答由已知条件做无向图由已知条件做无向图G=，其中其中 V=C1,C2,C6，E=(Ci,Cj)|S(Ci)S(Cj)，如图所示如图所示W6.给给G一种着色一种着色(点着色点着色)，Ci与与Cj着同色着同色 Ci与与Cj不相邻不相邻 没有学生既学没有学生既学Ci又学又学Cj Ci与与Cj可同时考可同时考.于是最少的考试时间为于是最少的考试时间为(G)=4（见定理（见定理17.21）