离散数学第章支配集覆盖集独立集匹配与着色.ppt

第十八章支配集、覆盖集、独立集、匹配与着色 主要内容 支配集、点覆盖集与点独立集 边覆盖与匹配 二部图中的匹配 点着色 地图着色与平面图的点着色 边着色 18.1 支配集、点覆盖集与点独立集 支配集与支配数 定义18.1 设G=V,E，V*?V. (1) V*为支配集——?vi?V?V*,?vj?V*，使得(vi,vj)?E (2) V*为极小支配集——V*的真子集不是支配集 (3) 最小支配集——元素最少的支配集 (4) 支配数?0(G)——最小支配集中的元素个数 极小与最小支配集之间的关系 最小支配集为极小支配集，但反之不真. 另外，极小支配集与最小支配集都可能不惟一. 又易知完全图、轮图、星形图的支配数均是1. 点独立集与点独立数 定义18.2 设G=V,E，V*?V. (1) 点独立集V*——V*中顶点彼此不相邻 (2) V*为极大点独立集——V*中再加入任何顶点就不是点独立集 (3) 最大点独立集——元素最多的点独立集 (4) 点独立数——最大点独立集中的元素个数，记为?0 极大独立集与极小支配集 定理18.1 设G=V,E中无孤立点，则G的极大点独立集都是 极小支配集. 点覆盖集与点覆盖数 定义18.3 设G=V,E, V*?V. (1) V*是点覆盖集——?e?E，?v?V*，使e与v关联 (2) V*是极小点覆盖集——V*的任何真子集都不是点覆盖集 (3) 最小点覆盖集(或最小点覆盖)——顶点数最少的点覆盖集 (4) 点覆盖数——?0(G)——最小点覆盖的元素个数 点覆盖集与点独立集的关系 定理18.2 设G=V,E无孤立点，V*?V，则V*是点覆盖当且 仅当为点独立集 18.2 边覆盖集与匹配 边覆盖集与边覆盖数 定义18.4 设G=V,E，E* ?E， (1) E* 为边覆盖集——?v?V，?e?E，使得v与e关联 (2) E* 为极小边覆盖——E* 的真子集不是边覆盖 (3) 最小边覆盖——边数最少的边覆盖 (4) 边覆盖数?1——最小边覆盖中元素个数 匹配(边独立集)与匹配数(边独立数) 定义18.5 设G=V,E, E*?E， (1) 匹配(边独立集)E*——E*中各边均不相邻 (2) 极大匹配E*——E*中不能再加其他边了 (3) 最大匹配——边数最多的匹配 (4) 匹配数——最大匹配中的边数，记为?1 关于匹配中的其他概念 定义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中的边交替出现构成的G中圈 可增广路径及交错圈 设红色边在匹配M中，绿色边不在M中，则图(1)中的两条路 径均为可增广的交错路径；(2)中的全不是可增广的交错路 径；(3)中是一个交错圈. 不难看出，可增广交错路径中，不在M中的边比在M中的边 多一条. 交错圈一定为偶圈. 最大匹配与最小边覆盖之间关系 定理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. 证明见教材. 推论 推论 设G是n阶无孤立顶点的图. M为G中的匹配，W是G中 的边覆盖，则 |M| ? |W|，等号成立时，M为G中完美匹配， W为G中最小边覆盖. 最大匹配判别定理 证明线索： 必要性. 若含可增广交错路径，可生成比M更大的匹配. 充分性. 设M和M1分别为不含可增广路径的匹配和最大匹 配，只要证明 |M|=|M1| 即可. 由必要性知，M1也不含可增广 交错路径. 设H = G[M1?M]，若H=?，M=M1，结论为真. 否 则H??. 此时，H中的交错圈(若存在)，其上M与M1的边 数相等，且所有交错路径上，M与M1中的边数也相等（因 为M与M1均无可增广路径）. 18.3 二部图中的匹配 定义18.7 设G=V1,V2,E为二部图，|V1|?|V2|，M是G中 最大匹配，若V1中顶点全是M饱和点，则称M为G中完备匹 配. |V1|=|V2| 时完备匹配变成完美匹配. Hall定理 定理18.5 （Hall定理）设二部图G=V1,V2,E中，|V1|?|