algorithm - 图中最大权重的循环

Question

给定一个加权图（有向或无向），我需要找到具有最大权重的图的循环。

循环的权重是图的边权重的总和。

它可以是任何循环，而不仅仅是我们可以的基本循环

• 查找所有基环（请参阅在无向图中识别所有环基的算法）
• 计算每个基本循环的权重并找到最大值

我可以尝试枚举图的所有循环，然后计算最大值，但循环的总数可能非常大（如果图是完整的，那么第一个和最后一个相同的任何顶点序列都是一个循环）。

您有什么想法可以在不枚举所有循环的情况下找到最大重量循环吗？

如果您需要图表上的假设（例如正权重），请指出它们。

Answer 1

这是 NP-Hard。

哈密​​顿循环问题可以简化为这个。

给定一个我们需要检查是否存在哈密顿循环的图，为每条边分配权重 1。

现在运行您的算法以获得最大重量循环。如果权重 < n，则原始图没有哈密顿圈，否则有。

Answer 2

如果您可以在特定情况下找到最小加权路径，只需反转所有权重的符号并应用您的算法。当然，您正在做出一些未说明的假设，因为 Moron 的论点是正确的（不是双关语）。您所做的假设可能是正权重或没有负权重周期。我认为您应该努力陈述它们，而不是让人们在可能假设的无限空间中搜索。至于硬度结果，这也很难以多种方式近似，请查看本文. 同一篇论文包含重要类型图的几个积极结果，但它涉及最长的未加权路径，所以我的猜测是论文中的大多数算法不会直接帮助你的情况。如果您搜索“重循环”，您会发现许多有趣的论文，但它们在性质上更具数学性。如果您的权重是小整数（最多为图形大小的多项式），您可以尝试用未加权的路径替换每条边，以将您的问题减少到未加权的情况。我希望这在一定程度上有所帮助，但你手上可能有一个开放的研究问题。