5.4 偶图、匹配及其应用.ppt_第1页
5.4 偶图、匹配及其应用.ppt_第2页
5.4 偶图、匹配及其应用.ppt_第3页
5.4 偶图、匹配及其应用.ppt_第4页
5.4 偶图、匹配及其应用.ppt_第5页
全文预览已结束

下载本文档

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

文档简介

1、5.4 偶图、匹配及其应用,定义1若无向图G=的结点集V能够划分为两 个子集V1, V2，满足V1V2，且V1V2V，使得 G中任意一条边的两个端点，一个属于V1，另一个属 于V2，则称G为偶图。记为G=. V1和V2称 为互补结点子集,在偶图G=中，若V1中的每个结点与V2 中的每个结点都有且仅有一条边相关联，则称偶图 G为完全偶图.记为Kn,m, 其中, n|V1|，m|V2|.,上图ad均是偶图，其中图b是完全偶图K2,3，图c 是完全偶图K3,3. 在图a中，G的互补结点子集为 V1=v1,v2,v3，V2=v4,v5,v6,v7； 在图d中，G的互补 结点子集为V1=v1,v2,v3

2、，V2=v4,v5,v6。事实上，图c 和图d是同一个图，它们都是完全偶图K3,3.,定理1 无向图G=为偶图的充分必要条件是G 的所有回路的长度均为偶数。,定义2 给定图G=，设M是E的一个不包含 环的子集，它的任意两条边在G均不相邻，则称M为 G匹配。 若匹配M的某条边与顶点v关联，则称v是M饱和 点，否则称v是M非饱和点 若G的每个顶点都是M饱和点，则称M为G完美匹 配，称含边数最多的匹配为最大匹配,设M为G的一个匹配，称G中由M中的边与非M中 的边交替组成的路为M交替路. 称起点与终点都为非饱和的为M交替路为M可扩 路.,定理1 (Berge,1957) G的匹配M为最大匹配当且仅当 G不包含M可扩路.,设S为图G的一个顶点子集，与S的顶点相邻的所 有顶点的集合，称为S的邻集. 记为N(S),偶图存在匹配的条件：设偶图G=, 1. 存在匹配的必要条件是|V1|V2|. 2. G存在饱和V1的每个点的匹配,当且仅当对V1的任一子集有: |N(S)| S| 3.如果满足条件 1) V1中每个结点至少关联t条边； 2) V2中每个结点至多关联t条边； 则G中存在从V1到 V2 的匹配,其中

人人文库> 全部分类> 行业资料 > 管理策划

温馨提示

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

最新文档

评论

0/150

提交评论