二分匹配算法理解

电玩女神 2022-05-17 12:58 145阅读 0赞

#                                          二分匹配算法理解 #

二分匹配算法是解决两个集合自身间的元素无关系，但两集合间的元素有关系，可将有关系的元素进行匹配，二分匹配可以得到最大匹配数；二分匹配是在一个集合中进行查找，查找不冲突就进行匹配，若出现冲突进行查找增广路，若找到增广路，更新原来的配对关系，具体实现是利用深搜思想查找尝试每一个点，首先从任意一个未被匹配的点u开始，从点u的边中任意选一条边开始配对。如果这个这条边连接的点还没有被配对此时便找到了一条增广路。如果这个点已将被配对了，就尝试进行“连锁反应”。如果尝试成功更新原来的配对关系。用一个match\[ \]数组实现，match\[ \]数组存储配对关系，初始化match\[ \]数组为0，例如当点u与点i配对成功match\[i\]=u；配对数加1；直到所有的点都尝试完，得到最大匹配数。

相关定义：

**最大匹配数**：最大匹配的匹配边的数目

**最小点覆盖数**：选取最少的点，使任意一条边至少有一个端点被选择

**最大独立集**：选取最多的点，使任意所选两点均不相连

**最小路径覆盖数**：对于一个 DAG（有向无环图），选取最少条路径，使得每个顶点属于且仅属于一条路径。路径长可以为 0（即单个点）。

定理1：**最大匹配数 = 最小点覆盖数**（这是 Konig 定理）

定理2：**最大独立集 = 顶点数 - 最小点覆盖数**

定理3：**最小路径覆盖数 = 顶点数 - 最大匹配数**

[https://blog.csdn.net/kongsanjin/article/details/81582888][https_blog.csdn.net_kongsanjin_article_details_81582888]

[https://blog.csdn.net/kongsanjin/article/details/81582928][https_blog.csdn.net_kongsanjin_article_details_81582928]

二分图的最大团

定义：对于一般图来说，团是一个顶点集合，且由该顶点集合诱导的子图是一个完全图，简单说，就是选出一些顶点，这些顶点两两之间都有边。最大团就是使得选出的这个顶点集合最大。对于二分图来说，我们默认为左边的所有点之间都有边，右边的所有顶点之间都有边。那么，实际上，我们是要在左边找到一个顶点子集X，在右边找到一个顶点子集Y，使得X中每个顶点和Y中每个顶点之间都有边。

方法：**二分图的最大团=补图的最大独立集**。

补图的定义是：对于二分图中左边一点x和右边一点y，若x和y之间有边，那么在补图中没有，否则有。

这个方法很好理解，因为最大独立集是两两不相邻，所以最大独立集的补图两两相邻。

[https://blog.csdn.net/kongsanjin/article/details/81588729][https_blog.csdn.net_kongsanjin_article_details_81588729]

Km算法：km算法和二分匹配的区别为二分匹配解决的是两个集合中的数配对使配对数最多，而km算法解决的也是两个集合进行配对只不过两集合间的组合数的权值不同km使最后配对的结果的权值和最大，在二分匹配中可以默认为权值都是相同的都为1；比如讲两集合分为x和y；km算法定义lx\[ \]数组和ly\[ \]数组及w\[ \]\[ \]数组，w数组存储每个集合x元素对每个集合y元素的权值，lx\[ \]数组初始为每个x对所有y中的最大值，ly\[ \]数组初始化为0，保证lx\[i\]+ly\[j\]>=w\[i\]\[j\]。开始进行匹配当匹配冲突后就d=lx\[i\]+ly\[j\]-w\[i\]\[j\]，对lx\[\]数组中已匹配过得点lx\[i\]进行更行lx\[i\]=lx\[i\]-d；对ly\[ \]数组中已匹配过得点进行更新ly\[j\]=ly\[j\]+d；更新后继续进行匹配，知道把所有能的点匹配完，最后循环找match\[ \]数组中存储的匹配的点，找出对应的w\[match\[i\]\]\[i\]权值加在一起的到最大权值和。

[https://blog.csdn.net/kongsanjin/article/details/81588648][https_blog.csdn.net_kongsanjin_article_details_81588648]

[https_blog.csdn.net_kongsanjin_article_details_81582888]: https://blog.csdn.net/kongsanjin/article/details/81582888
[https_blog.csdn.net_kongsanjin_article_details_81582928]: https://blog.csdn.net/kongsanjin/article/details/81582928
[https_blog.csdn.net_kongsanjin_article_details_81588729]: https://blog.csdn.net/kongsanjin/article/details/81588729
[https_blog.csdn.net_kongsanjin_article_details_81588648]: https://blog.csdn.net/kongsanjin/article/details/81588648