美好的人生来自匹配_第1页
美好的人生来自匹配_第2页
美好的人生来自匹配_第3页
美好的人生来自匹配_第4页
美好的人生来自匹配_第5页
已阅读5页，还剩6页未读， 继续免费阅读

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

1、美好的人生来自匹配如何才能更好的匹配！如何才能获得更美好的人生，就让我们一起领略匹配的奥妙吧！LETS GO问题提出：10个人分12本书，每名同学分到一本想要的书，尽管本数多与学生，但这个问题可能无解 从这个问题抽象出的图模型G 此图的顶点为学生 和书 显然G是一个二部图 如图8.1所示 例8.1由于在考试中获得好成绩，6名学生，A,B,C,D,E,F将获得a,c,d,g,h,p,t，7种不同的书中的一本，每名同学的喜好不同A：d,h,t B：g,h,t C：a,g,h D：h,p,t E：a,c,d F：c,d,p问：每名同学是否可以得到他喜欢的书？例8.2 7名大学生B,D,F,J,K,L

2、,M毕业后找工作，大学就业办只有 a,c,e,p,r,s,t七个职位，每名学生申请的职位如下，问：每名学生能否得到所申请的职位？定理8.3 设G为二部图，其部集为U和W，且r=|U| |W|。则G包含一个基数为r的匹配当且仅当U是友好的定理8.3的证明很精彩，大家肯定很想听一下它的推论 推论：设 为非空有限集合，若存在n个不同的元素 使得 则称该集族有一个互异代表元系。互异代表元系。为了使得集合 有一个互异代表元系，则必须定理 8.4 非空有限集 有一个互异代表元系，当且仅当对于任一整数 k（1kn ），集族中任意k个集合的并至少包含k个元素 TH8.5（婚姻定理）在一个由r个女人和s个男人构成的人群中， 1rs，在熟悉的男女之间可能出现r对婚姻当且仅当对每个整数k（ 1kr），任意k个女人共认识至少k个男人TH8.6 任意一个r正则二部图(r 1)均有一个完美匹配TH8.7 对于任意不包含孤立点的n阶图G，TH8.8 对于任意不包含孤立点的n阶图，点覆盖数 覆盖所有边的顶点的最小个数点独立数 相互不邻接的顶

人人文库> 全部分类> 教育资料 > 课件下载

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论