从加权图中选择边，使每个顶点都是一条边的端点，并且边权重的总和最小化

Question

对于简化，我们可以假设图G=(V，E(有2N个顶点，并且答案有N条边。

我已经了解到，如果图是二分图，匈牙利算法可以很好地工作。然而，我想知道对于一般图是否有任何非平凡的解(即多项式解(。

任何多项式解，以及NP复杂性的证明，都是受欢迎的。

Answer 1

如果您希望每个顶点都恰好与一条边相关，那么您需要找到完美匹配。但是，即使对于具有偶数顶点的图，也不总是存在完全匹配。

你可以在这个答案中看到例子。