《14-支配-独立-覆盖-匹配--天津大学》由会员分享，可在线阅读，更多相关《14-支配-独立-覆盖-匹配--天津大学（30页珍藏版）》请在金锄头文库上搜索。
1、六年级数学上册课件-比的基本性质和化简比江苏省连云港市田家炳中学高一生物现代生物进化理论的主要内容课件八一建军节 主题教育活动PPT模板军队 国防改革强军梦学习第十三章 支配,覆盖,独立,匹配六年级数学上册课件-比的基本性质和化简比江苏省连云港市田家炳中学高一生物现代生物进化理论的主要内容课件八一建军节 主题教育活动PPT模板军队 国防改革强军梦学习群体中的独特子集一个年级，有若干个班长；只要通知班长，就可以通知到所有同学。在若干城市中建立中心台站，使得其他城市均与中心台站相邻，同时 又使得中心台站的数量尽可能少。在一个计算机网络中确定若干关键结 点，可以通过这 些节点检验 全 部的线路。在超
2、市中设置收款台，使得顾客在任何一个通道都能看到至少一个收 款台。在大量纷繁复杂的随机变量中，找到一个子集，使得子集中的变量相 互之间独立。将一群年轻人根据他们之间的关系来配对，使得尽可能多的人被配对 。六年级数学上册课件-比的基本性质和化简比江苏省连云港市田家炳中学高一生物现代生物进化理论的主要内容课件八一建军节 主题教育活动PPT模板军队 国防改革强军梦学习支配,覆盖,独立,匹配六年级数学上册课件-比的基本性质和化简比江苏省连云港市田家炳中学高一生物现代生物进化理论的主要内容课件八一建军节 主题教育活动PPT模板军队 国防改革强军梦学习支配集 P190 - 定义13.1无向图G=, 支配集:
3、 V* V 使得 u V-V*, v V*, uEv 一个顶顶点子集，使得不属于这这个子集的顶顶点都与集合内的某 顶顶点相邻邻。（通过事物【顶点】的一部分【子集】，利用 特 定关系【边】控制事物的全体）极小支配集: V*是支配集, 其真子集都不是最小支配集: |V*|最小的支配集支配数: 0(G)=|V*|, V*是最小支配集六年级数学上册课件-比的基本性质和化简比江苏省连云港市田家炳中学高一生物现代生物进化理论的主要内容课件八一建军节 主题教育活动PPT模板军队 国防改革强军梦学习群体中的独特子集一个年级，有若干个班长；只要通知班长，就可以通知到所有同学。在若干城市中建立中心台站，使得其他城
4、市均与中心台站相邻，同时 又使得中心台站的数量尽可能少。在一个计算机网络中确定若干关键结 点，可以通过这 些节点检验 全 部的线路。在超市中设置收款台，使得顾客在任何一个通道都能看到至少一个收 款台。在大量纷繁复杂的随机变量中，找到一个子集，使得子集中的变量相 互之间独立。将一群年轻人根据他们之间的关系来配对，使得尽可能多的人被配对 。六年级数学上册课件-比的基本性质和化简比江苏省连云港市田家炳中学高一生物现代生物进化理论的主要内容课件八一建军节 主题教育活动PPT模板军队 国防改革强军梦学习支配集(例)星形图Sn: v0,v1,v2,vn-1, 0(Sn)=1轮图 Wn: v0,v1,v3,
5、v5,vn-2, 0(Wn)=1v0v1v2v3v5v4六年级数学上册课件-比的基本性质和化简比江苏省连云港市田家炳中学高一生物现代生物进化理论的主要内容课件八一建军节 主题教育活动PPT模板军队 国防改革强军梦学习定理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
6、六年级数学上册课件-比的基本性质和化简比江苏省连云港市田家炳中学高一生物现代生物进化理论的主要内容课件八一建军节 主题教育活动PPT模板军队 国防改革强军梦学习支配,覆盖,独立,匹配六年级数学上册课件-比的基本性质和化简比江苏省连云港市田家炳中学高一生物现代生物进化理论的主要内容课件八一建军节 主题教育活动PPT模板军队 国防改革强军梦学习点覆盖 P190 - 定义13.3无向图G=点覆盖: V* V e E, v V*, v关联e 一个顶顶点的子集，使得所有的边边都与子集中的某顶顶点关联联 (找出一组事物【顶点】，使得由这些事物可以找到所有的 关系【边】)极小点覆盖: V*是点覆盖, 其真子
7、集都不是最小点覆盖: |V*|最小的点覆盖点覆盖数: 0(G)=|V*|, V*是最小点覆盖六年级数学上册课件-比的基本性质和化简比江苏省连云港市田家炳中学高一生物现代生物进化理论的主要内容课件八一建军节 主题教育活动PPT模板军队 国防改革强军梦学习群体中的独特子集一个年级，有若干个班长；只要通知班长，就可以通知到所有同学。在若干城市中建立中心台站，使得其他城市均与中心台站相邻，同时 又使得中心台站的数量尽可能少。在一个计算机网络中确定若干关键结 点，可以通过这 些节点检验 全 部的线路。在超市中设置收款台，使得顾客在任何一个通道都能看到至少一个收 款台。在大量纷繁复杂的随机变量中，找到一个
8、子集，使得子集中的变量相 互之间独立。将一群年轻人根据他们之间的关系来配对，使得尽可能多的人被配对 。六年级数学上册课件-比的基本性质和化简比江苏省连云港市田家炳中学高一生物现代生物进化理论的主要内容课件八一建军节 主题教育活动PPT模板军队 国防改革强军梦学习点覆盖(例)v0,v1,v3,v5, v1,v2,v3,v4,v5,v6, 0=4v0v1v2v3v5六年级数学上册课件-比的基本性质和化简比江苏省连云港市田家炳中学高一生物现代生物进化理论的主要内容课件八一建军节 主题教育活动PPT模板军队 国防改革强军梦学习讨论连通图中，点覆盖一定是支配集？YES！极小点覆盖一定是极小支配集？NO！
9、反例: v0,v1, v3,v5是极小点覆盖, v1,v3,v5是极小支配集支配集一定是点覆盖？NO！反例: v1,v4是支配集,不是点覆盖 v0v1v2v3v5六年级数学上册课件-比的基本性质和化简比江苏省连云港市田家炳中学高一生物现代生物进化理论的主要内容课件八一建军节 主题教育活动PPT模板军队 国防改革强军梦学习边覆盖无向图G=边覆盖: E* E ， v E, e E*, e关联v 所有边边的一个子集，任意顶顶点均与子集中的某条边边关联联(一 个能包含所有事物的关系集合)极小边覆盖: E*是边覆盖, 其真子集都不是最小边覆盖: |E*|最小的边覆盖边覆盖数: 1(G)=|E*|, E*
10、是最小边覆盖六年级数学上册课件-比的基本性质和化简比江苏省连云港市田家炳中学高一生物现代生物进化理论的主要内容课件八一建军节 主题教育活动PPT模板军队 国防改革强军梦学习边覆盖(例)e2,e3,e6, e2,e3,e7, 1=3e1e2 e3e4e6e7e5e1e2 e3e4e6e7e5e1e2 e3e4e6e7e5六年级数学上册课件-比的基本性质和化简比江苏省连云港市田家炳中学高一生物现代生物进化理论的主要内容课件八一建军节 主题教育活动PPT模板军队 国防改革强军梦学习支配,覆盖,独立,匹配六年级数学上册课件-比的基本性质和化简比江苏省连云港市田家炳中学高一生物现代生物进化理论的主要内容
11、课件八一建军节 主题教育活动PPT模板军队 国防改革强军梦学习独立集 P190 - 定义13.2无向图G=独立集: V* V u,v V*, (u,v) E 一个顶顶点的子集，其中任意两个顶顶点之间间没有边边相连连（根 据 给定关系【边】，找出一个互不干扰的事物集合）极大独立集: V*是独立集, 其真母集都不是最大独立集: |V*|最大的独立集独立数: 0(G)=|V*|, V*是最大独立集六年级数学上册课件-比的基本性质和化简比江苏省连云港市田家炳中学高一生物现代生物进化理论的主要内容课件八一建军节 主题教育活动PPT模板军队 国防改革强军梦学习群体中的独特子集一个年级，有若干个班长；只要通
12、知班长，就可以通知到所有同学。在若干城市中建立中心台站，使得其他城市均与中心台站相邻，同时 又使得中心台站的数量尽可能少。在一个计算机网络中确定若干关键结 点，可以通过这 些节点检验 全 部的线路。在超市中设置收款台，使得顾客在任何一个通道都能看到至少一个收 款台。在大量纷繁复杂的随机变量中，找到一个子集，使得子集中的变量相 互之间独立。将一群年轻人根据他们之间的关系来配对，使得尽可能多的人被配对 。六年级数学上册课件-比的基本性质和化简比江苏省连云港市田家炳中学高一生物现代生物进化理论的主要内容课件八一建军节 主题教育活动PPT模板军队 国防改革强军梦学习独立集(例)v0, v1,v4, v
13、1,v3,v5, 0=3v0v0v0六年级数学上册课件-比的基本性质和化简比江苏省连云港市田家炳中学高一生物现代生物进化理论的主要内容课件八一建军节 主题教育活动PPT模板军队 国防改革强军梦学习定理2: 无向图G无孤立点,V*是极大独立集,则V*也是极 小支配集.证明: V*是极大独立集,则V*也是支配集.(反证: 否则, u V-V*, v V*, (u,v) E, V* u还是独立集,矛盾.) V*是极小支配集(反证: 否则, u V*, V*-u是支配集, 则 v V*, (u,v) E, 与V*是独立集相矛盾.) 逆命题题不成立： 极小支配集不一定是极大独立集定理13.2 P190
14、- 定理13.2六年级数学上册课件-比的基本性质和化简比江苏省连云港市田家炳中学高一生物现代生物进化理论的主要内容课件八一建军节 主题教育活动PPT模板军队 国防改革强军梦学习定理3: 无向图G无孤立点, V* V, V*是点覆盖 V-V*是独立集.证明: ( ) (反证) 否则, u,v V-V*, (u,v) E, V*不是点覆盖,矛盾. ( ) V-V*是独立集, (u,v) E, u V-V* v V-V*, u V* v V*, V*是点覆 盖. 推论: 无向图G无孤立点, V*是极(最)小点覆盖 V-V*是极(最)大独立集 .0+0=n.定理13.3 P191 - 定理13.3六年
15、级数学上册课件-比的基本性质和化简比江苏省连云港市田家炳中学高一生物现代生物进化理论的主要内容课件八一建军节 主题教育活动PPT模板军队 国防改革强军梦学习团 P191 - 定义13.4无向图G=, V* V团: GV*是完全子图极大团: V*是团, 其真母集都不是最大团: |V*|最大的团团数: 0(G)=|V*|, V*是最大团六年级数学上册课件-比的基本性质和化简比江苏省连云港市田家炳中学高一生物现代生物进化理论的主要内容课件八一建军节 主题教育活动PPT模板军队 国防改革强军梦学习团(例)v0,v1,v2, v1,v2, v1, 0(G)=3v0v1v2六年级数学上册课件-比的基本性质和化简比江苏省连云港市田家炳中学高一生物现代生物进化理论的主要内容课件八一建军节 主题教育活动PPT模板军队 国防改革强军梦学习定理13.4 P191 - 定理13.4定理13.4: 无向图G, V*是G的团 V*是G补的独立集. 推论: 无向图G, V*是G的极(最)大团 V*是G补的极(最 )大独立集. 0(G)=0(G补).六年级数学上册课件-比的基本性质和化简比江苏省连云港市田家炳中学高一生物现代生物进化理论的主要内容课件八一建军节
