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

Question

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

例如...匈牙利算法、贝尔曼-福特算法甚至 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 是最大匹配的假设相矛盾。