匹配在graph 是一组成对的顶点不相交的边，如果它覆盖了尽可能多的边，则它是最大值图中的顶点。有有效的算法来查找此类匹配以及实现（请参见例如 Boost 为 C++ 示例）。
然而，任意图中可以存在多个最大匹配；是否有任何算法的实现可以让您列出所有这些算法？我更喜欢 C++ 实现，但其他语言也可以。
A matching in a graph is a set of pairwise vertex-disjoint edges, and it is maximum if it covers the largest possible number of vertices in the graph. There are efficient algorithms for finding such matchings, as well as implementations (see e.g. Boost for an example in C++).
However, there can be several maximum matchings in an arbitrary graph; are there any implementations of algorithms that allow you to list all of them? I would prefer C++ implementations, but other languages are fine too.
发布评论
评论（2）
“枚举二部图中所有完美、最大和最大匹配的算法” -
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.107.8179&rep=rep1&type=pdf
“计算匹配数和弦和二部和弦
图类” -
http://www.jaist.ac.jp/~okamotoy/PDF/matchchordal .pdf
我希望这能对您有所帮助。
"Algorithms for Enumerating All Perfect, Maximum and Maximal Matchings in Bipartite Graphs" -
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.107.8179&rep=rep1&type=pdf
"Counting the Number of Matchings in Chordal and Chordal Bipartite
Graph Classes" -
http://www.jaist.ac.jp/~okamotoy/PDF/matchchordal.pdf
I hope this can help you somehow.
T. Uno（与上面 Piotr 给出的第一个参考文献中的作者相同）在 2001 年的论文中解决了在一般图中找到所有最大匹配的问题：
枚举非二分最大匹配的快速算法
现在最大（基数）匹配通常是最大匹配的严格子集，但是一旦知道最大匹配的大小，就可以轻松过滤最大匹配以消除除最大匹配之外的所有匹配。
然而，T. Uno 提出的这种“快速算法”的时间复杂度取决于最大匹配的数量。事实上对于一般图 G(V,E) 和 |V|顶点和 |E|边，时间复杂度为 O(|E|+|V|+Δ*N)，其中 Δ 是顶点的最大度数，N 是最大匹配数。
当最大匹配与最大匹配的比率很高时，这并不理想。然而，该算法适用于一般图，因此在仅搜索最大匹配时期望这种行为似乎相当合理。
The problem of finding all maximum matchings in general graphs is addressed by T. Uno (the same author as in the first reference given by Piotr, above) in this 2001 paper:
A Fast Algorithm for Enumerating Non-Bipartite Maximal Matchings
Now maximum (cardinality) matchings are generally a strict subset of the maximal matchings, but once the size of a maximum matching is known, the maximal matchings are easily filtered to eliminate all but the maximum matchings.
However the time complexity of this "fast algorithm" proposed by T. Uno is dependent on the number of maximal matchings. Indeed for a general graph G(V,E) with |V| vertices and |E| edges, the time complexity is O(|E|+|V|+Δ*N), where Δ is the maximum degree of vertices and N is the number of maximal matchings.
This would not be ideal when the ratio of maximal matchings to maximum matchings is high. However the algorithm applies to general graphs, so it seems fairly reasonable to expect this sort of behavior in searching only for maximum matchings.