最大赋权的匹配_with_向边 [英] Maximum weighted bipartite matching _with_ directed edges

问题描述

我知道不同的算法来计算的加权，无向二分图的最大权重匹配（即分配问题）：

I know various algorithms to compute the maximum weighted matching of weighted, undirected bipartite graphs (i.e. the assignment problem):

例如...匈牙利算法，贝尔曼 - 福特甚至花算法（它适用于一般的，即不是二分，图表）。

For instance ... The Hungarian Algorithm, Bellman-Ford or even the Blossom algorithm (which works for general, i.e. not bipartite, graphs).

但是，我怎么能计算最大权重匹配，如果二分图的边缘权和指挥

However, how can I compute the maximum weighted matching if the edges of the bipartite graph are weighted and directed?

我会AP preciate指针算法，polinomial复杂或之前转换，使图无向，这样我可以应用任何上述算法。

I would appreciate pointers to algorithms with polinomial complexity or prior transformations to make the graph undirected so that I could apply any of the aforementioned algorithms.

编辑：注意的匹配应尽量边的权重，这就是为什么有向边有差别（A-> B可以有一个完全不同的权重比B-> A）。

note that the matching should maximize the weight of the edges, that's why having directed edges makes a difference (A->B can have a totally different weight than B->A).

当然，如果我是最大化基数，向边不会有所作为，我可以申请任何众所周知的算法，以最大限度地提高基数：Hopcroft - 卡普，最大网络流量....

Admittedly, if I was maximizing cardinality, the directed edges wouldn't make a difference and I could apply any of the well-known algorithms to maximize cardinality: Hopcroft–Karp, Maximum Network Flow ....

编辑2 ：既然的匹配的是通常适用于无向图中的术语，让我澄清我用的究竟意味着匹配的在这个问题上：一组有向边不共享开始或结束顶点的。更确切地讲，如果U-> V和U' - > V'，是配套的一部分，那么V / = U'和V'/ = U

Edit 2: Since matching is a term normally applied to undirected graphs, let me clarify what I exactly mean by matching in this question: a set of directed edges that do not share start or end vertices. More formally, if U->V and U'->V' are part of the matching, then V /= U' and V' /= U.

推荐答案

DFB的评论是正确的，任何两个顶点A，B，你可以抛弃这两个边缘的便宜AB和BA。

dfb's comment is correct, for any two vertices A, B you can discard the cheaper of the two edges AB and BA.

证明是一个班轮：

定理：最大匹配并购从来没有包含AB的任何两个顶点A，B更便宜的优势和学士学位。

Theorem: A maximum matching M never contains the cheaper edge of AB and BA for any two vertices A,B.

证明：设M是一个最大匹配。假设AB是M和比BA便宜。定义M'= M - {AB} + {BA}。 M'显然还是匹配的，但它更昂贵。这contraditcs是m是一个最大匹配的假设。

Proof: Let M be a maximum matching. Suppose AB is in M and is cheaper than BA. Define M' = M - {AB} + {BA}. M' is clearly still a matching, but it's more expensive. That contraditcs the assumption that M was a maximum matching.

这篇关于最大赋权的匹配_with_向边的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！