algorithm - 偶数个顶点的高效完美匹配算法？

Question

检测具有偶数个顶点的图中是否存在完美匹配的最有效算法是什么？

Answer 1

编辑:正如 NiklasB 所指出的，我给出的第一个答案是不正确的。

更正我在下面所说的内容(有关以下段落的更深入讨论，请参阅 1):首先，图特矩阵是一个形式变量矩阵，所以它的行列式是一个形式变量的多项式，而不是一个数。由于 T 是形式矩阵，计算其行列式可能需要指数时间。然而，我们不需要真正计算 det(T) 只是测试它是否完全相同的 0 多项式。这意味着对于 T 中变量的每个数值赋值，det(T) 将产生 0。可以进一步证明，如果不存在完美匹配，对于大多数变量赋值，det (T) 将评估为非零变量。因此，我们可以用随机值代替 T 中的变量并计算行列式。如果我们评估为非零值，我们可以安全地说不存在匹配。否则，如果我们重复此操作足够次数，我们就会获得所需的置信度，可以说确实存在完美匹配。

该算法仍然受取行列式的运行时间的限制。当前最有效的已知算法的运行时间为 O(n^2.373)，在本例中为 O(|V|^2.373)。这是什么意思？

Edmond 有 O(|E|sqrt(|V|))。

对于某些类型的图，尤其是密集图，这实际上可以渐近地击败 Edmond 的。但就像我提到的，这仍然是一个随机算法，而不是一个精确的算法。

编辑评论:它的一个好处是，与 Edmonds 相比，它更容易让您的头脑围绕一个实际的工具展开。用 C 实现 Edmond 是我本科生涯中最悲伤的夜晚之一。

原始错误答案:您可以使用 Tutte 矩阵找到完美匹配的存在:http://en.wikipedia.org/wiki/Tutte_matrix

如果 A(t) 是图 G(V,E) 的 tutte 矩阵，则存在完美匹配当且仅当 det(A) != 0。您可以在 O(n^3) 中找到行列式通过高斯消元法进行操作，在本例中为 O(|V|sqrt(|V|))。如果 O(|E|) > O(|V|)，这是对 Edmonds 的 O(|E|sqrt(|V|)) 运行时间的改进。