定向最大加权二分匹配允许共享起始/结束顶点

Question

设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以下定义新的无向图.

1. G'有一个节点(A, B),w每个有向边(A, B)的权重w,权重为G
2. G'((A, B),(B, C))如果(A,B)和(B,C)都是G中的有向边,则具有无向边

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

现在找到一个最大(加权)的独立顶点集G'.

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

编辑:此点之后的东西仅在所有边权重相同时起作用 - 当边权重具有不同的值时,这是一个更难的问题(对于可能的算法,谷歌"最大权重独立顶点集")

通常,这将是NP难问题.但是,它G'是一个二分图 - 它只包含偶数周期.在二分图中找到最大(加权)独立顶点集不是 NP难的.

您将运行的算法G'如下.

1. 找到连接的组件G',比方说H_1, H_2, ..., H_k
2. 对于每个H_i节点做2色(比如红色和蓝色).这里的食谱方法是对H_i交替颜色进行深度优先搜索.一个简单的办法是在彩色每个顶点H_i基于在相应的边缘是否G从进U给V(红色)或从V到U(蓝色).
3. 要从H_i中选择节点的两个选项是所有红色节点或所有蓝色节点.选择具有较高权重的彩色节点集.例如,红色节点集的权重等于H_i.nodes.where(node => node.color == red).sum(node => node.w).调用较高权重的节点集N_i.
4. 您的最大加权独立顶点集现在是union(N_1, N_2, ..., N_k).

由于每个顶点G'对应于其中一个有向边G,因此您具有最大的DirectionalMatching.