如果图在 python 中不是二分图，如何找到最小权重完美匹配
how to find the minimum-weight perfect matching if the graph is not bipartite in python
wiki中完美匹配的概念：
A perfect matching is a matching that matches all vertices of the
graph. That is, a matching is perfect if every vertex of the graph is
incident to an edge of the matching.
所以最小权重完美匹配是权重最小的组合之一。起初，我的想法是遵循贪心算法（注意：我的图是完整的，每个顶点都有到其余顶点的边）：
从图中选取一个顶点，并在每一步中找到它最近的邻居顶点，然后将它们丢弃并进行循环，直到图中没有顶点。但是，除非计算 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)
然后搜了一篇blossom belief propagation的文章，不知道能不能实现，有什么想法吗？
您可以将最小权重匹配减少到最大权重匹配
您可以反转图形中的所有边权重，方法是乘以 -1 或从最大权重中减去它们。然后，如果您可以在此转换后的图中找到最大完美匹配，则该匹配在您的原始图中是最小的。
nx.algorithms.matching.max_weight_matching 具有参数 maxcardinality，如果设置为 True，则意味着如果存在这样的匹配，它将只允许完全匹配。因此，您可以在转换后的图形上调用 networkx 函数并检查匹配是否确实完成。如果是，这个匹配就是你想要的结果。如果不是，那么完美匹配是不可能的。
对于偶数个顶点的完全图，完全匹配当然总是可能的。此外，如果转换后的图只有正权重（例如使用基于减法的转换），则最大权重图将始终具有最大基数。
wiki中完美匹配的概念：
A perfect matching is a matching that matches all vertices of the graph. That is, a matching is perfect if every vertex of the graph is incident to an edge of the matching.
所以最小权重完美匹配是权重最小的组合之一。起初，我的想法是遵循贪心算法（注意：我的图是完整的，每个顶点都有到其余顶点的边）：
从图中选取一个顶点，并在每一步中找到它最近的邻居顶点，然后将它们丢弃并进行循环，直到图中没有顶点。但是，除非计算 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)
然后搜了一篇blossom belief propagation的文章，不知道能不能实现，有什么想法吗？
您可以将最小权重匹配减少到最大权重匹配
您可以反转图形中的所有边权重，方法是乘以 -1 或从最大权重中减去它们。然后，如果您可以在此转换后的图中找到最大完美匹配，则该匹配在您的原始图中是最小的。
nx.algorithms.matching.max_weight_matching 具有参数 maxcardinality，如果设置为 True，则意味着如果存在这样的匹配，它将只允许完全匹配。因此，您可以在转换后的图形上调用 networkx 函数并检查匹配是否确实完成。如果是，这个匹配就是你想要的结果。如果不是，那么完美匹配是不可能的。
对于偶数个顶点的完全图，完全匹配当然总是可能的。此外，如果转换后的图只有正权重（例如使用基于减法的转换），则最大权重图将始终具有最大基数。