是否有一种算法可以找到在有向图中弱连接的 DAG 的最大权重，其中每个切割都有弱连接的集合（从一个集合到另一个集合至少有一条有向路径）？或者这是一个NP难题？关于这个主题的上一个问题没有指定https://mathoverflow.net/questions/31864/algorithms-for-maximum-weighted-spanning-connected-dag-directed-acyclic-graph弱连接或强连接，所以我想成为更精确。
问问题
1404 次
2 回答
5
希望这不会太晚。对于上述案例，Kruskal 和 Prim 都很容易失败。考虑一个 2 节点图：A --> B（权重 10），B --> A（权重 6），B --> A（权重 6）（是：从 B 到 A 的两条边；图中没有任何内容排除了！）。Kruskal 会首先选择 A --> B 边缘并卡住。Prim 会选择从 B 到 A 的边缘之一，然后卡住。最大。加权无环子图是包含从 B 到 A 的两条边的子图。它是一个子图，它是无环的！
最好的拉维
于 2013-09-20T22:36:44.137 回答
0
您的弱连接条件似乎只是底层无向图是连接的。这很容易；您可以使用 Kruskal 或 Prim 或任何您最喜欢的最小生成树算法。
最小权重强连通子图是 NP 完全的；观察到任何这样的子图至少有 |V| 边缘并且它正好有 |V| 边当且仅当它是哈密顿循环。
您可能希望选择一个顶点作为“根”，并要求在子图中有一条从每个顶点到根的路径。这就是“最小扩展树状结构”问题。正如@matejpavouk 指出的那样，由于 Chu、Liu 和 Edmonds，有一个二次算法。
于 2012-12-27T00:50:08.723 回答