2

我知道各种算法来计算加权无向二部图的最大加权匹配（即分配问题）：

例如......匈牙利算法、Bellman-Ford 甚至 Blossom 算法（适用于一般的，即非二分图）。

但是，如果二部图的边是加权和定向的，我如何计算最大加权匹配？

我会很感激具有多项式复杂性或先验变换的算法的指针，以使图形无向，以便我可以应用上述任何算法。

编辑：请注意，匹配应该使边缘的权重最大化，这就是为什么有向边缘会有所不同（A->B 的权重可能与 B->A 的权重完全不同）。

诚然，如果我要最大化基数，则有向边不会产生影响，我可以应用任何众所周知的算法来最大化基数：Hopcroft–Karp，最大网络流量......

编辑2：由于匹配是一个通常应用于无向图的术语，让我澄清一下我在这个问题中匹配的确切含义：一组不共享开始或结束顶点的有向边。更正式地说，如果 U->V 和 U'->V' 是匹配的一部分，则 V /= U' 和 V' /= U。

4

1 回答 1

2

dfb 的评论是正确的，对于任意两个顶点 A、B，您可以丢弃两条边 AB 和 BA 中较便宜的那个。

证明是单行的：

定理：对于任意两个顶点 A，B，最大匹配 M 永远不会包含 AB 和 BA 的便宜边。

证明：设 M 为最大匹配。假设 AB 在 M 中并且比 BA 便宜。定义 M' = M - {AB} + {BA}。M' 显然仍然是一个匹配项，但它更昂贵。这与 M 是最大匹配的假设相矛盾。

于 2013-02-12T02:52:34.993 回答