最大加权二部匹配_with_有向边

Question

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

比如说..。匈牙利算法，Bellman，甚至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是最大匹配的。