康奈尔 CS6820 算法分析讲义
需积分: 5 30 浏览量
2024-02-01
14:44:18
上传
评论
收藏 2.73MB PDF 举报
康奈尔大学，2016年秋季学期 CS 6820：算法
讲义：二分图匹配算法 8月24日至9月2日
这些笔记分析了涉及二分图匹配的优化问题的算法。 匹配算法不仅在自身中很有用（
例如，在网络中将客户与服务器匹配，或在市场中将买家与卖家匹配），而且还为学习图
算法理论和算法中的许多重复主题提供了一个具体的起点。这些主题的例子包括增广路径
、线性规划松弛和原始-对偶算法设计。
1 二分图最大匹配
在本节中，我们介绍了二分图最大匹配问题，提出了一个时间复杂度为 O(mn)的朴素算
法，然后介绍和分析了由Hopcroft和Karp提出的将运行时间改进为 O(m
√
n)的算法。
1.1 定义
定义1.在无向图中，一个匹配是一组边，使得没有顶点属于该组的超过一个元素。
当我们将一个二分图 G表示为有序三元组 G= (U, V, E)时，表示 U和 V是构成 G顶点
的不相交集合，并且 G的每条边都有一个端点（左端点）在 U中，另一个端点（右端点）
在 V中。
定义2.二分图最大匹配问题是在二分图中计算具有最大基数的匹配的问题。
我们将假设二分图最大匹配问题的输入 G =(U, V, E)以其邻接表表示给出，并且 G的
二分划分——即将顶点集划分为 U和 V——作为问题的一部分给出。
练习1.证明如果二分图的划分没有作为输入的一部分给出，可以从 G的邻接表表示中在线
性时间内构建出来。
（在CS 6820的讲义中，我们将提供一些练习来帮助你理解。鼓励你尝试解决这些练习，
但它们不是作业问题，我们不会检查你是否解决了它们，更不会评分你的解答。）
1
剩余102页未读，继续阅读
资源评论
