algorithm - 从加权图中选择边，使得每个顶点都是一条边的端点，边权重之和最小

Question

为简单起见，我们可以假设图 G=(V,E) 有 2N 个顶点，答案有 N 条边。

我了解到，如果图是二分图，匈牙利算法效果很好。但是，我想知道一般图是否有任何非平凡的解决方案（即多项式解决方案）。

欢迎任何多项式解决方案以及 NP 复杂性的证明。

标签： algorithmgraph

Answer 1

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

您可以在此答案中看到示例。