MIT 18.433：二分图匹配理论与组合优化

"MIT 18.433 组合优化讲义.pdf" 这篇讲义主要探讨了组合优化中的一个重要领域——二分图匹配。二分图是一种特殊的图，其顶点可以被划分为两个互不相交的集合A和B，其中任意一条边连接的两个顶点分别属于这两个集合。在二分图中，匹配是指边的集合，其中每条边连接一对不同的顶点，而不会有任何顶点被两条边同时连接。匹配可以是不完美的，即存在未匹配的顶点，也可以是完美的，当所有顶点都被匹配时。 讲义首先介绍了几个基本概念，如图的定义（由顶点和边组成）、二分图、匹配以及未匹配顶点。接着，它提出了两个关键问题：1) 最大基数匹配问题，目标是寻找二分图中最大的匹配；2) 最小权重完美匹配问题，这涉及到给定每条边的权重，找到总权重最小的完美匹配。后者也称为分配问题。 对于最大基数匹配问题，讲义提到可以通过证明匹配大小的上界来确定最优解，这涉及到图论中的对偶概念。顶点覆盖是另一个相关概念，它是一个包含所有边至少一个端点的顶点集合。讲义指出最大匹配的大小总是小于等于最小顶点覆盖的大小，这是弱对偶性的体现。König定理（1931年）进一步指出，在二分图中，最大匹配的大小实际上等于最小顶点覆盖的大小，显示了强对偶性。 接下来，讲义会描述算法来解决这些问题，特别是匈牙利算法，它是一种高效的方法，用于找到二分图的最大匹配。此外，可能还会涉及增广路径的概念，它是证明和构造最大匹配的关键工具。增广路径是匹配中的一种特殊路径，通过调整它可以增加匹配的大小，直到达到最大匹配。 在最小权重完美匹配问题中，可能会引入Edmonds算法，该算法结合了增广路径的思想和权重的概念，能够在有向二分图中找到最小权重的完美匹配。此算法对于理解和求解分配问题至关重要。 这篇讲义深入讲解了二分图匹配理论及其在组合优化中的应用，不仅涵盖基础理论，还涉及实际求解这些问题的算法。这些内容对于理解图论、优化理论以及相关领域的研究者和学生来说都是非常宝贵的资源。