的最大重量的曲线图周期曲线图、周期、重量、最大
给出一个加权图（向或无向），我需要找到该图的最大权重的周期。
Given a weighted graph (directed or undirected) I need to find the cycle of the graph with the maximum weight.
一个周期作为图的边的权重的总和的重量
The weight of a cycle being the sum of the weight of the edges of the graph.
它可以是任何周期，而不仅仅是基本周期的，我们可以
It can be any cycle, not just base cycle for which we can
找到所有的基本周期（见http://stackoverflow.com/questions/1607124/algorithms-to-identify-all-the-cycle-bases-in-a-undirected-graph ） 计算各基地循环的重量并找到最大我可以尝试以枚举图的所有周期，然后计算最大但周期的总数目可真大（如果图形是完整然后顶点，其中第一和最后一个是相同的任何序列是一个周期）。
I could try to enumerate all cycles of the graph and then compute the maximum but the total number of cycles can be really big (if the graph is complete then any sequence of vertices where the first and last one are identical is a cycle).
你有什么想法，发现最大重量周期不枚举所有周期？
Do you have any idea to find that maximum weight cycle without enumerating all cycles ?
如果您需要在图形上（阳性权重为例）的假设，请指示他们。
If you need hypothesis on the graph (positives weights for example) please indicates them.
推荐答案
这是NP难。
Hamilton回路问题可减小到这个
Hamiltonian Cycle problem can be reduced to this.
给定一个曲线图，我们需要检查是否存在一个汉密尔顿的周期与否，分配权重为每个边缘。
Given a graph for which we need to check if there exists a Hamiltonian Cycle or not, assign weight 1 to each edge.
现在运行你的算法，以获得最大的权重周期。如果重量为＆lt; n，则原来的图没有哈密顿圈，否则它的作用。
Now run your algorithm to get the maximum weight cycle. If the weight is < n, then the original graph has no Hamiltonian cycle, otherwise it does.
