匹配与覆盖匹配与覆盖1工作安排问题工作安排问题2匹配与覆盖及其应用匹配与覆盖及其应用系统监控问题系统监控问题3建模案例：锁具装箱问题建模案例：锁具装箱问题4一、匹配与覆盖一、匹配与覆盖1、基本概念、基本概念定义定义1 设图设图若若M的边互不相邻，则称的边互不相邻，则称M是是G的一个的一个匹配匹配。M的边称为匹配边，的边称为匹配边，EM的边称为的边称为自由边自由边。若若则称则称u(或或v)是是v(或或u)的的配偶配偶。若顶点。若顶点v与与M的一的一条边关联，则称条边关联，则称v是是M-饱和的饱和的；否则称为是；否则称为是M-非饱和的非饱和的。设。设M是是G的一个匹配，若的一个匹配，若G的每个顶点都是的每个顶点都是M-饱和的，则称饱和的，则称M是是G的的完美完美(理想理想)匹配匹配。设。设M是是G的一个匹配，若不存在匹配的一个匹配，若不存在匹配使使则称则称M为为G的的最大匹配最大匹配。说明说明 显然，显然，完美匹配一定是最大匹配，反之不一定成立完美匹配一定是最大匹配，反之不一定成立。(a)所示的匹配所示的匹配(匹配边用粗线表示，下同匹配边用粗线表示，下同)是最大匹配但不是最大匹配但不是完美
