algorithm - 图中最大权重的循环

Question

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

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

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

• 找到所有碱基循环(参见 Algorithms to Identify All the Cycle Bases in a UnDirected Graph)
• 计算每个基循环的权重并找出最大值

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

您是否知道在不枚举所有循环的情况下找到最大重量循环？

如果您需要图表上的假设(例如正权重)，请注明。

Answer 1

这是 NP-Hard。

Hamiltonian Cycle 问题可以简化为这样。

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

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