如果图不是python中的二部图，如何找到最小权重完美匹配

Question

维基中完美匹配的概念：

完美匹配是匹配图的所有顶点的匹配。也就是说，如果图的每个顶点都与匹配的边相关，则匹配是完美的。

所以最小权重完美匹配是权重最小的组合之一。起初，我的想法是遵循贪心算法（注意：我的图是完整的，每个顶点都有到其余顶点的边）：

从图中挑选一个顶点，并在每一步中找到它最近的邻居顶点，然后丢弃它们并循环直到图中没有顶点。然而，除非计算 n! 次：

while odd_vert:
    v = vertices.pop()
    length = float("inf")
    closest = 0
    for u in odd_vert:
        if graph[v][u]["weight"] < length:
            length = graph[v][u]["weight"]
            closest = u
    graph_minimum_match.add_edge(v, closest, weight = length)

我在 networkx 中找到了一些函数，但它要求图形是二分的：

nx.algorithms.bipartite.matching.minimum_weight_full_matching(G, top_nodes=None, weight='weight')

此外，找到最大的权重匹配：

nx.algorithms.matching.max_weight_matching(G, maxcardinality=True)

然后，我搜索了一篇关于开花信仰传播的文章，但我不确定它是否可以实现，所以有什么想法吗？

Answer 1

您可以将最小权重匹配减少到最大权重匹配

您可以通过乘以 -1 或从最大权重中减去它们来反转图中的所有边权重。然后，如果您可以在这个转换后的图中找到最大的完美匹配，那么原始图中的匹配是最小的。

nx.algorithms.matching.max_weight_matching具有参数maxcardinality，如果设置为True，则表示仅在存在此类匹配时才允许完全匹配。因此，您可以networkx在转换后的图形上调用该函数并检查匹配是否确实完成。如果是，则此匹配是您想要的结果。如果不是，则不可能完美匹配。

在具有偶数个顶点的完整图中，完全匹配当然总是可能的。此外，如果转换后的图只有正权重（例如通过使用基于减法的转换），则最大权重图将始终具有最大基数。