algorithm - 从加权图中选择边，这样每个顶点都是一个边的端点，并且边权重的总和被最小化

为了简化，我们可以假设图G=（V，E）有2N个顶点，而答案有N个边。
我已经了解到如果图是二部的，匈牙利算法可以很好地工作但是，我想知道对于一般图是否有非平凡解（即多项式解）。
任何多项式解，以及NP复杂度的证明，都是受欢迎的。

最佳答案

如果你希望每个顶点都恰好与一条边相关联，那么你需要找到完美的匹配。但即使对于偶数个顶点的图，也不总是存在完全匹配。
您可以在this answer中看到示例。