[2018年必威体育精装版整理]29-匹配070101.ppt

匹配 信号处理中的数学方法 第2-10讲 上一讲内容的回顾 图的平面嵌入 平面图和非平面图 平面图的必要条件：欧拉公式 适用于简单图的欧拉公式推论 平面图的充分必要条件-Kuratowski定理 平面图着色与四色定理 匹配 支配集 点覆盖集与独立集 边覆盖集 匹配 最大匹配和完美匹配 二部图中的匹配 Hull定理 支配集与支配数 点 支配 点 u 受u支配的顶点集合 支配数 ?0=2 u 支配数 ?0=1 极小支配集 最小支配集 点独立集与独立数 (点)独立集: 点与点 不 相邻 独立数 ?0=3 独立数 ?0=2 最大独立集 极大独立集 独立集与支配集的关系 设G是无孤立点的简单无向图，则G的极大独立集都是极小支配集。 证明： 设V*是任意的极大独立集 (i) V*必是支配集。假设不是，则?v0?VG-V*, v0与V*中任何元素均不相邻，则V*?{v0}仍是独立集，矛盾。 (ii) V*是极小的。设v‘是V*中任一元素， 因为V*是独立集，V*-{v’}中任何元素 都不能支配v, ?V*-{v}不是支配集。 注意：极小支配集未必是最大独立集 (甚至未必是独立集) 极小支配集 不是 独立集 点覆盖与点覆盖数 点 覆盖 边 点覆盖数 ?0=4 点覆盖数 ?0=3 最小点覆盖 极小点覆盖 点覆盖与点独立集的关系 设G是无孤立点的简单无向图，VG的真子集V*是点覆盖当且仅当V-V*是点独立集。 证明：令V’=V-V* ? 假设V不是独立集，则存在u,v?V, 满足uv?EG, 注意：V‘=VG-V*, 即u,v?V*, ?uv边不可能被V*所覆盖，矛盾。 ? ?e?EG, 假设e=uv, 因为V‘是点独立集，u,v中至少有一个不在V中，不妨设u?V, 则u?V*, ?V* 是点覆盖。 边覆盖与边覆盖数 边 覆盖 点 边覆盖数 ?1=3 极小边覆盖 最小边覆盖 匹配 边 独立 集 – 匹配: 边与边 不 相邻 匹配数 ?1=3 匹配数 ?1=4 极大匹配 最大匹配 完美匹配 M-饱和点 M-饱和点 最小边覆盖与最大匹配的关系 (无孤立点的简单无向图中，最大匹配总是某个最小边覆盖的子集。) 若M是图G中的最大匹配, 对G中每个M-非饱和点，取一条与之相关联的边，构成边集N W=M?N 是G中的最小边覆盖 若W1是图G中的最小边覆盖，若N1是为了消除W1中的相邻边所需移去的最小的边集 M1=W1-N1 是G中的最大匹配 最小边覆盖与最大匹配的关系 证明W是最小边覆盖，M1是最大匹配． W显然是边覆盖，所以 |W|??1。注意：|M|=?1, 又因为M是最大匹配，N中不可能有一条边的两个端点都是M-非饱和点，? |N|=n-2?1，?|W|=|M|+|N|=n-?1。 而M1=W1-N1显然是匹配, |M1|??1。因为W1是最小边覆盖，构造M1时，每移去一条边，恰好产生一个M1-非饱和点。注意：|W1|=?1, M1-非饱和点数为n-2|M1|，?|N1|=|W1|-|M1|=n-2|M1|, 即?1= n-|M1|。 综上所述可得：?1= n-|M1|?n-?1=|W|??1, 于是：|W|=?1且|M1|=?1，即W是G中的最小边覆盖，且M1是G中的最大匹配。 推论：?1+?1=n。 由匹配决定的交错路 定义：设M是G中一个匹配。若G中路径P中M与EG-M中的边交替出现，则称P为M-交错路(也可以是回路)；若P的起点与终点都是M-非饱和点，则称P是可增广交错路。 可增广交错路 最大匹配的特征 M是G中最大匹配当且仅当G中不含M-可增广交错路。 证明： ?　设M是最大匹配。若G中含可增广路P，显然，M?EP仍是匹配，且边数比M多1，矛盾。 ? 设G中不含可增广路，假设M是G的一个最大匹配。设H是M?M边诱导子图。若H=?, M=M, 即M是最大匹配。否则，因为M和M均为匹配，H中不可能有3次或3次以上的顶点，H的每个连通分支只能是交错回路或交错路，在两种情况下，H中取自M和M的边总是一样多(否则，M和M中有一个含可增广路)，?M是最大匹配。 二部图中的完备匹配 定义：设G是二部图，二部划分为V1,V2，若G中的匹配M饱和V1中所有顶点，则称M为完备匹配。 注意：完备匹配一定是最大匹配，但仅当|V1|=|V2|才是完美匹配。 此图无完备匹配 存在完备匹配的充分必要条件 Hull定理：二部图G=(V1,V2, E), |V1|?|V2|, 存在完备匹配当且仅当V1中任意k个顶点至少与V2中的k个顶点相邻，其中k=1,2,…|V1|。 证明(必要性显然，只需证明充分