图中最大重量的循环

Question

给定加权图（有向或无向图），我需要找到最大权重的图周期。

循环的重量是图形边缘重量的总和。

它可以是任何周期，而不仅仅是我们可以的基本周期

• 找到所有基本周期（请参阅 算法以识别无向图中的所有循环基础 )
• 计算每个基本周期的重量并找到最大

我可以尝试枚举图形的所有循环，然后计算最大周期，但是循环总数确实很大（如果图形完成，那么第一个和最后一个相同的顶点序列是一个循环）。

您是否有任何想法在不枚举所有周期的情况下找到最大的重量周期？

如果您需要在图表上的假设（例如，阳性权重），请指示它们。

Answer 1

这是NP-HARD。

汉密尔顿周期问题可以减少。

给定图表，我们需要检查是否存在哈密顿周期，请为每个边缘分配权重1。

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

Answer 2

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