支配独立覆盖匹配天津大学.ppt

支配,覆盖,独立,匹配 匹配 P193 – 定义13.6 无向图G=V,E 匹配(边独立集): E*?E ，?e,f?E*, e,f不相邻 边的一个子集，子集中任意两条边不相邻（顶点不重合） （若干对不同事物之间的二元关系） 极大匹配: E*是匹配, 其真母集都不是 最大匹配: |E*|最大的匹配 匹配数: ?1(G)=|E*|, E*是最大匹配 群体中的独特子集 一个年级，有若干个班长；只要通知班长，就可以通知到所有同学。 在若干城市中建立中心台站，使得其他城市均与中心台站相邻，同时又使得中心台站的数量尽可能少。 在一个计算机网络中确定若干关键结点，可以通过这些节点检验全部的线路。 在超市中设置收款台，使得顾客在任何一个通道都能看到至少一个收款台。 在大量纷繁复杂的随机变量中，找到一个子集，使得子集中的变量相互之间独立。 将一群年轻人根据他们之间的关系来配对，使得尽可能多的人被配对。 …… 匹配(例) {e1,e7}, {e1,e4}, {e5}, ?1=2 e1 e2 e3 e4 e6 e7 e5 e1 e2 e3 e4 e6 e7 e5 e1 e2 e3 e4 e6 e7 e5 e1 e2 e3 e4 e6 e7 e5 完美匹配 完美匹配: 没有非饱和点的匹配 e1 e2 e3 e4 e6 e7 e5 e8 e1 e2 e3 e4 e6 e7 e5 e8 总结 支配集,极（最）小支配集 点覆盖,极（最）小点覆盖 独立集,极（最）大独立集 团，极（最）大团 支配集，点覆盖，独立集以及团之间的关系 匹配与完美匹配 《集合论与图论》第26讲 《集合论与图论》第26讲 《集合论与图论》第26讲 《集合论与图论》第26讲 《集合论与图论》第26讲 《集合论与图论》第26讲 《集合论与图论》第26讲 《集合论与图论》第26讲 第十三章 支配,覆盖,独立,匹配 群体中的独特子集 一个年级，有若干个班长；只要通知班长，就可以通知到所有同学。 在若干城市中建立中心台站，使得其他城市均与中心台站相邻，同时又使得中心台站的数量尽可能少。 在一个计算机网络中确定若干关键结点，可以通过这些节点检验全部的线路。 在超市中设置收款台，使得顾客在任何一个通道都能看到至少一个收款台。 在大量纷繁复杂的随机变量中，找到一个子集，使得子集中的变量相互之间独立。 将一群年轻人根据他们之间的关系来配对，使得尽可能多的人被配对。 …… 支配,覆盖,独立,匹配 支配集 P190 - 定义13.1 无向图G=V,E, 支配集: V*?V 使得?u?V-V*, ?v?V*, uEv 一个顶点子集，使得不属于这个子集的顶点都与集合内的某 顶点相邻。（通过事物【顶点】的一部分【子集】，利用特 定关系【边】控制事物的全体） 极小支配集: V*是支配集, 其真子集都不是 最小支配集: |V*|最小的支配集 支配数: ?0(G)=|V*|, V*是最小支配集 群体中的独特子集 一个年级，有若干个班长；只要通知班长，就可以通知到所有同学。 在若干城市中建立中心台站，使得其他城市均与中心台站相邻，同时又使得中心台站的数量尽可能少。 在一个计算机网络中确定若干关键结点，可以通过这些节点检验全部的线路。 在超市中设置收款台，使得顾客在任何一个通道都能看到至少一个收款台。 在大量纷繁复杂的随机变量中，找到一个子集，使得子集中的变量相互之间独立。 将一群年轻人根据他们之间的关系来配对，使得尽可能多的人被配对。 …… 支配集(例) 星形图Sn: {v0},{v1,v2,…,vn-1}, ?0(Sn)=1 轮图Wn: {v0},{v1,v3,v5…,vn-2}, ?0(Wn)=1 v0 v1 v2 v3 v5 v4 定理1: 无向图G无孤立点,V1*是极小支配集,则存在V2*也是极小支配集,且V1*?V2*=?. 证明: V1*是极小支配集,则V-V1*也是支配集.(反证: 否则, ?u?V1*, ?v?V-V1*, (u,v)?E, V1*-{u}还是支配集,矛盾.) V-V1*是支配集,则V-V1*中有子集是极小支配集,设为V2*. 则V1*?V2*=?. 定理13.1 P190 - 定理13.1 支配,覆盖,独立,匹配 点覆盖 P190 - 定义13.3 无向图G=V,E 点覆盖: V*?V ?e?E, ?v?V*, v关联e 一个顶点的子集，使得所有的边都与子集中的某顶点关联 (找出一组事物【顶点】，使得由这些事物可以找到所有的 关系【边】) 极小点覆盖: V*是点覆盖, 其真子集都不是 最小点覆盖: |V*|最小的点覆盖 点覆盖数: ?0(G)=|V*|, V*是最小点覆盖 群体中的独特子集 一