文件名称：最大匹配的大小-ansi-vita 62-2016 modular power supply standard
文件大小：2.84MB
文件格式：PDF
更新时间：2024-06-29 16:21:28
集训队论文集
4.1 最大匹配的大小 到目前为止，我们的所有算法都是用来求解完美匹配的，但在实际应用中我们要求解 的往往是最大匹配。 与之前解决完美匹配问题的思路类似，我们先从最简单的问题入手：对于一个给定的 图 G = (V, E)，如何求出图 G的最大匹配的大小 ν(G)？对于这个问题，我们有如下定理 定理 4.1. 图 G的最大匹配的大小 ν(G)是 12 rank Ã(G)。 证明. 设 k = rank Ã(G)。由推论 3.6，我们可以选出 Ã(G)的一个行号集合 I = {i1, i2, . . . , ik}， 使得 rank Ã(G) = rank Ã(G)I,I = k。设 U = {vi1 , vi2 , . . . , vik }，那么 Ã(G)I,I = Ã(G[U])。由于 rank Ã(G[U]) = |U |，因此图 G[U]存在完美匹配，这说明 ν(G) ≥ k2。 如果 ν(G) > k2，我们考虑取出所有在最大匹配中的点，那么一定存在一个行号集合 I， 使得 |I| > k 并且 det Ã(G)I,I , 0，这意味着 Ã(G)的子矩阵的秩大于它本身的秩，显然这是 不可能的。 综上，ν(G) = k2。 � 4.2 转化一 接下来我们尝试把最大匹配转化为我们所熟悉的完美匹配问题。如果对于一个图 G， 我们已经求出它的最大匹配的大小 ν(G)了，那么我们可以在图 G 的基础上新增 n − 2ν(G) 个点，并从新加进来的点往之前 n个点的每一个连边，这样得到的新图就是一个有完美匹 配的图了，并且这个新图的完美匹配与原图的最大匹配相对应。 这样我们就解决了最大匹配问题。这个转化的通用性非常好，但它有一个缺点，在最 坏情况下我们可能要新增 n个点，这将使我们的数据规模（点数）翻倍，因此将会显著增 大算法的常数。 4.3 转化二 我们考虑另一个做法，同样是将最大匹配问题转化为完美匹配问题，不过这次我们将 通过删点来实现。对于一个图 G = (V, E)和它的一个最大匹配 M，我们考虑所有在匹配 M 中的点构成的点集 U，显然 G[U]有完美匹配，并且 G[U]的完美匹配就是 G的最大匹配。 现在我们的思路就是设法找出这样的点集 U，然后对 G[U] 应用我们之前求解完美匹配的 算法。 实际上定理 4.1的证明过程已经为我们指明了方向。由引理 3.5和推论 3.6，我们只需 要找到 Ã(G)的一组关于行的极大线性无关组就可以了。这可以通过一遍高斯消元求出来。 23