21

令 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：在我研究解决问题的过程中，我发现了这篇论文，我认为这对试图找到解决方案的其他人会有所帮助：Alternating cycles and paths in edge-colored multigraphs: a survey

注意 3：如果有帮助，您也可以将图视为等效的 2 边彩色无向二部多重图。然后问题公式将变成：找到具有最大权重和的没有颜色交替路径或循环的边集。

注 4：我怀疑这个问题可能是 NP 难的，但我对减少没有那么经验，所以我还没有设法证明它。

又一个例子：

想象一下你有

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

4条边：{u1->v1, u1->v2, u2->v1, v2->u2}

那么，不管它们的权重如何，u1->v2和v2->u2不能在同一个DirectionalMatchingv2->u2中，和也不能u2->v1。但是u1->v1and u1->v2can, and so can u1->v1and u2->v1.

4

2 回答 2

10

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

  1. G'每个有向边都有一个权重的节点(A, B)，权重为w(A, B)wG
  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-hard 问题。然而，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。

于 2013-02-20T22:13:11.600 回答
-2

这个问题可以使用匈牙利算法在多项式时间内解决。上面 Vor 的“证明”是错误的。

上述示例的问题结构化方法如下：

   D E F
A  # 7 9  
B  1 # #
C  # 3 #

其中“#”表示负无穷大。然后，您使用匈牙利算法解析矩阵以确定最大匹配。如果要找到最小匹配，可以将数字乘以 -1。

于 2013-02-19T19:02:25.697 回答