离散数学 课件5.1-二部图_第1页
离散数学 课件5.1-二部图_第2页
离散数学 课件5.1-二部图_第3页
离散数学 课件5.1-二部图_第4页
离散数学 课件5.1-二部图_第5页
已阅读5页，还剩18页未读， 继续免费阅读

付费下载

下载本文档

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

文档简介

第六章再论图论离散数学讲授：李小南配套教材：李小南，易黄建，乔胜宁，离散数学，电子工业出版社，2025目录CONTENTS6.16.26.36.46.5二部图最大匹配及稳定匹配图的连通性平面图图的顶点着色6.1二部图

二部图和匹配有工作申请者和n项工作,每项工作最多由一个人来做且每个人可接受的工作有若干种,能否有一种工作安排方案,使得n个人都能得到自己满意的工作?可以用图对这一问题建立模型:图的顶点分别为申请者和工作,若人a满意工作j,就用一条边连接a和j.这样问题就变为是否可以找出n条相互之间无公共顶点的边.上述模型中图的顶点集可以分为两个集合,使得每个集合中的顶点互不相邻,这样的图称为二部图,模型中需要寻找的相互无公共顶点的边集称为图的匹配.

定理5.1.1(könig,1936)一个图是二部图当且仅当它不含奇圈.证明：必要性.二部图中的闭合通道都是从某个部集出发往返于两个部集间最后再回到出发的部集,经过了偶数步,也即二部图的闭合通道都是偶数长的.故二部图不含奇圈.定理5.1.1(könig,1936)

一个图是二部图当且仅当它不含奇圈.

定理5.1.1(könig,1936)

一个图是二部图当且仅当它不含奇圈.证明：充分性.

顶点覆盖

街道上需要有警察来维持治安,假设交叉路口的警察可以监管和路口相连的街道,我们往往关心最少安排多少警察可以监管整个街道网络？把上面问题抽象成图论中的模型,我们就有了下面顶点覆盖的概念.

在左图中，等式成立,而右图中最小顶点覆盖大小为3,而最大匹配大小为2.注意左图为二部图,其实我们有定理5.1.3定理5.1.3(König-Egerváry,1931)设G是(X,Y)-二部图,则G的最大匹配的大小等于G的最小顶点覆盖的大小.

定理5.1.3(König-Egerváry,1931)设G是(X,Y)-二部图,则G的最大匹配的大小等于G的最小顶点覆盖的大小.

Hall定理有许多证明方法,我们这里利用König-Egerváry定理证明了Hall定理,也可利用Hall定理证明König-Egerváry定理.另外,Hall定理告诉我们可以通过的某些子集的邻域顶点太少来说明不存在浸润(X,Y)-二部图中部集X的匹配.最后我们指出匹配理论是组合数学及最优化学科中最经典且最为重要的内容之一,在诸多领域有着广泛应用.

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

温馨提示

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

最新文档

评论

0/150

提交评论