Zyklus des Maximalgewicht in einem Graphen

Question

ein gewichteter Graph Given (gerichtet oder ungerichtet) Ich brauche den Zyklus des Graphen mit dem maximalen Gewicht zu finden.

Das Gewicht eines Zyklus die Summe aus dem Gewicht der Kanten des Graphen ist.

Es kann jeder Zyklus sein, nicht nur Basiszyklus, für den wir können

• finden Sie alle Zyklus Basis (siehe Algorithmen zu Identifizieren All Zyklus Bases in einem ungerichteten Graphen)
• berechnen das Gewicht eines jeden Zyklus Basis und finden Sie das Maximum

könnte ich versuchen, alle Zyklen des Graphen aufzuzählen und dann das Maximum zu berechnen, aber die Gesamtzahl der Zyklen kann wirklich groß sein (wenn der Graph vollständig ist dann eine beliebige Folge von Eckpunkten, wo die erste und letzte identisch sind, ist ein Zyklus ).

Haben Sie eine Idee haben, dass die maximale Gewicht Zyklus zu finden, ohne alle Zyklen aufzählt?

Wenn Sie Hypothese auf dem Graphen (positive Gewichte zum Beispiel) benötigen Sie zeigt an sich.

Answer 1

Dies ist NP-Hard.

Hamilton-Zyklus Problem kann auf diese reduziert werden.

Bei einem Graphen, für die wir brauchen, um zu überprüfen, ob es ein Hamilton-Zyklus vorhanden ist oder nicht, assign Gewicht 1 bis jede Kante.

Führen Sie nun Ihr Algorithmus das maximale Gewicht Zyklus zu erhalten. Wenn das Gewicht

Answer 2

Wenn Sie die minimale gewichtete Pfad in Ihrem speziellen Fall finden, Reverse nur die Zeichen aller Gewichte und Ihren Algorithmus anwenden. Natürlich machen Sie einige unausgesprochene Annahmen weil Moron Argument korrekt ist (kein Wortspiel beabsichtigt). Die Annahmen, die Sie machen könnten positive Gewichte oder keine negativen Gewichtszyklen. Ich glaube, Sie sollten sich bemühen, ihnen zu erklären, statt Menschen in den unendlichen Raum der möglichen Annahmen suchen zu lassen. In Bezug auf Härte ergibt, ist dies auch schwer in einer Reihe von Art und Weise zu nähern Besuche dieses Papier . Das gleiche Papier enthält einige positive Ergebnisse für wichtige Arten von Grafiken, aber es beschäftigt sich mit längste ungewichteten Pfade so meine Vermutung, dass die meisten Algorithmen in dem Papier wird nicht direkt helfen, in Ihrem Fall. Wenn Sie für „Heavy Zyklen“ suchen Sie eine Reihe von interessanten Papieren finden, aber sie sind mehr mathematisch Charakter. Wenn Ihre Gewichte kleine ganze Zahlen sind (bis zu einem Polynom in der Größe der Grafik), können Sie versuchen, und jede Kante mit einem ungewichteten Pfad ersetzen Ihr Problem auf den ungewichteten Fall zu reduzieren. Ich hoffe, dies bis zu einem gewissen Grad hilft, aber Sie könnten ein offenes Forschungsproblem an den Händen haben.