针对最大加权匹配二部允许开始/结束顶点的共享(Directed maximum weighted b

让G（U U V，E）是一个加权有向二部图（即U和V是两个集合的二部图的节点和E包含向加权边缘从u到v或从V到U）。下面是一个例子：

在这种情况下：

U = {A,B,C} 
V = {D,E,F} 
E = {(A->E,7), (B->D,1), (C->E,3), (F->A,9)}

定义：DirectionalMatching（我做了这个词只是为了让事情更清晰）：设置可以共享的开始或结束顶点向边。也就是说，如果U-> V和U ' - > V'两者都属于DirectionalMatching然后V / = U '和V'/ = U，但它可以是U = U '或V = V'。

我的问题：如何有效地找到DirectionalMatching，如上面所定义，双边定向加权图最大化其边缘的权重的总和？

通过有效的 ，我的意思是多项式复杂或更快，我已经知道如何实现一个幼稚的蛮力方法。

在最大加权DirectionalMatching上面的例子是：{F-> A，C-> E，B-> d}，具有13的值。

正式证实这一问题的等价性，以图论中的任何其他众所周知的问题，也将是有价值的。

谢谢！

注1：这个问题是基于最大加权二分匹配_with_向边，但与额外的放松，这是允许的边缘匹配共享始发地或目的地。由于该松弛，使一个很大的区别，我创建了一个独立的问题。

注2：这是一个最大权重匹配。基数（多少边缘是存在的）且由匹配覆盖顶点的数量是无关正确的结果。只有最大重量的事项。

注2：在我的研究来解决，我发现本文中的问题，我认为这将是帮助他人试图找到一个解决方案：交替边缘色重图的循环和路径：一项调查

注3：如果有帮助，你也可以认为该图形为等值2边有色无向二部多重图。那么问题制剂将变成： 查找边的集合，而不具有最大权重和颜色交替路径或周期。

注4：我怀疑问题可能是NP难，但我不认为有减少经历，所以我还没有成功地证明这一点呢。

另一个例子 ：

想象一下，你有

4个顶点{u1, u2} {v1, v2}

4个边缘{u1->v1, u1->v2, u2->v1, v2->u2}

然后，不管他们的权重， u1->v2和v2->u2不能在同一DirectionalMatching，既不可以v2->u2和u2->v1 。然而u1->v1和u1->v2就可以了，所以可以u1->v1和u2->v1 。

Answer 1:

定义一个新的无向图G'从G如下。

http://en.wikipedia.org/wiki/Line_graph#Line_digraphs

现在发现的最大（加权）独立顶点在设置G' 。

http://en.wikipedia.org/wiki/Vertex_independent_set

通常，这将是一个NP难问题。但是， G'是一个二分图-它仅包含偶数周期。寻找最大（加权）独立顶点在二部图集不是 NP难解。

你会在运行该算法G'如下。

找到的连接部件G' ，说H_1, H_2, ..., H_k
对于每个H_i做2着色（说红色和蓝色）的节点。这里的菜谱的做法是做一个深度优先搜索H_i交替的颜色。一个简单的办法是在彩色每个顶点H_i基于在相应的边缘是否G从进入U到V （红色）或从V到U （蓝色）。
对于哪些节点从中选择两个选项H_i要么所有的红色节点或所有蓝色节点。选择颜色的节点集与更高的权重。例如，红色节点组具有重量等于H_i.nodes.where(node => node.color == red).sum(node => node.w) 呼叫设置较高权重节点N_i 。
你的最大加权独立顶点集现在union(N_1, N_2, ..., N_k)