algorithm - 最大加权二分匹配_with_有向边

Question

我知道各种算法来计算加权、无向二分图的最大加权匹配(即分配问题):

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

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

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

编辑:请注意，匹配应该最大化边的权重，这就是为什么有向边会产生差异(A->B 的权重可能与 B->A 完全不同)。

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

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

Answer 1

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

证明是单行的:

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

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