没有合适的资源？快使用搜索试试~ 我知道了~

文库首页课程资源C/C++二部图概述（二分图，匹配，覆盖，KM算法）

二部图概述（二分图，匹配，覆盖，KM算法）

二分图，匹配，覆盖，KM算法

5星 · 超过95%的资源需积分: 34 44 下载量 134 浏览量 2012-05-01 21:57:09 上传评论 3 收藏 555KB PPT 举报

温馨提示

试读

33页

二分图的最大匹配，匈牙利算法，最小点覆盖，DAG图的最小路径覆盖。二分图的最大独立集.二分图最优匹配.noi,acm,基础

资源详情

资源评论

二分图匹配

Bi-partite graph

二分图的定义：

二分图是这样的一个图，它的顶点可

以分为两个集合 X 和 Y 。所有的边关联的两个

顶点中，恰好一个属于集合 X ，一个属于集合

Y 。

二分图的匹配：

给定一个二分图

G ， M 为 G 边集的一个子集，

如果 M 满足当中的任意两条

边都不依附于同一个顶点，则

称 M 是一个匹配。

二分图的最大匹配



定义：

图中包含边数最多的匹配称为图

的最大匹配。

如右图所示：蓝色部分

就构成一个最大匹配，

同时它也是一个完美匹

配

完美匹配：如果所有点都在匹配边上，称这个最大

匹配是完美匹配。

二分图的最大匹配



匈牙利算法（时间复杂度 O(nm) ）



其思想是用宽度优先搜索来找增广路径（和

oodll 算法类似



转化为单位容量简单网络的最大流问题



在二分图的基础上，加入源点 s 和汇点 t ，让

s 与每个 X 结点连一条边，每个 Y 结点和 t 连

一条边，所有弧的容量为 1 。这样，饱和弧就

对应着匹配边。

二分图的最大匹配



匈牙利算法：



寻找增广路：



初始时最大匹配为空

for 二分图左半边的每个点 i

do 从点 i 出发寻找增广路径



如果找到，则把它取反



（即增加了总了匹配数）。



看一道例题： PKU 1469

剩余32页未读，继续阅读

评论收藏

内容反馈

changhong0214

2013-06-13

内容比较容易懂

最新资源

(源码)基于Spring Boot和Vue的后台管理系统.zip
用于将 Power BI 嵌入到您的应用中的 JavaScript 库查看文档网站和 Wiki 了解更多信息 .zip
(源码)基于Arduino、Python和Web技术的太阳能监控数据管理系统.zip
(源码)基于Arduino的CAN总线传感器与执行器通信系统.zip
(源码)基于C++的智能电力系统通信协议实现.zip
用于 Java 的 JSON-RPC.zip
用 JavaScript 重新实现计算机科学.zip
(源码)基于PythonOpenCVYOLOv5DeepSort的猕猴桃自动计数系统.zip
用 JavaScript 编写的贪吃蛇游戏 .zip
(源码)基于ASP.NET Core的美术课程管理系统.zip

szbsxb

粉丝: 0
资源: 1

上传资源快速赚钱

前往需求广场，查看用户热搜

二部图概述（二分图，匹配，覆盖，KM算法）

评论2

最新资源

相关推荐

二分图最大匹配km算法

二分图匹配

二分图匹配 KM算法 匈牙利算法

二分图最大匹配及最大权匹配（km算法）

二分图匹配问题（匈牙利及KM算法）

二分图匹配算法总结1

二分图匹配算法（C++实现）

二分图PPT(匈牙利算法，KM算法详解)

二分图完备匹配(匈牙利算法)

KM算法C++源代码

二分图匹配 匈牙利算法和KM算法简介.ppt

二分图匹配匈牙利算法和KM算法简介.pptx

matlab实现匈牙利算法二分图最大匹配的程序

二分图的最优匹配（KM算法）.doc

二分图的完美匹配 KM算法.docx

广告商收益化最大问题_M?n_KM算法_二分图最大匹配_

二分图的最优匹配算法

二分图最大匹配算法

KM算法PPT讲解分析

信息安全数学基础（许春香）

Warshall算法(邻接矩阵到可达矩阵)

km算法C++实现

最大二分图分配

判断一个连通无向图是否为二部图

二分图匹配-匈牙利算法和KM算法简介.pptx

二分图匹配-匈牙利算法和KM算法简介 精品资料.pptx

二分图匹配 KM算法匈牙利算法

二分图匹配匈牙利算法和KM算法简介.ppt

二分图匹配-匈牙利算法和KM算法简介精品资料.pptx