14
第5-1课：匈牙利算法与二分图的最大匹配
source link: https://blog.csdn.net/orbit/article/details/108729353
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
在图论中，二分图（又称二部图）是一个特殊的模型，关于二分图有很多概念，比如匹配、完全匹配、最大匹配等。这一课我们来介绍一种求二分图的最大匹配的匈牙利算法，匈牙利算法原理是公开的，人们使用匈牙利算法都是根据自己问题域的数据模型，利用算法原理实现具体的算法。这一课我们的关注点仍然是怎么根据算法原理设计数据模型，并实现算法。
二分图的各种匹配
首先介绍一下二分图，二分图 G=(V,E) 是这样的一个图，它的顶点集合 V 可以划分为 X 和 Y 两个集合，它的边集合 E 中的每条边都有一个端点在 X 集合，另一个端点在 Y 集合。判断二分图的关键是看点集是否能分成两个独立的点集，如图（1-a）就是一个二分图，如果一个图的边形成了三角形，那它一定不是二分图，图（1-b）就不是二分图。
图（1）二分图识别示意图
对于一个二分图 G=(V,E) 中部分边组成的子集 M，如果 M 的边集中任意两条边都不依附于同一个顶点，则称 M 是一个匹配，怎么理解这句话呢？首先匹配是一个边的集合，并且不唯一；其次，匹配 M 中没有任何两条边有公共的顶点。以图（1-a）所示的二分图为例，图（2-a）和图（2-b）中红色的边集就是二分图的两个匹配，而图&
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK