Cycle de poids maximal dans un graphe

Question

Étant donné que je dois trouver le cycle du graphique avec le poids maximum d'un graphe pondéré (dirigé ou non orienté).

Le poids d'un cycle étant la somme des poids des arêtes du graphe.

Il peut être un cycle, pas seulement le cycle de base pour lesquels nous pouvons

• trouver tout le cycle de base (voir algorithmes pour identifier toutes les bases de cycle dans un graphe non orienté )
• calculer le poids de chaque cycle de base et trouver le maximum

Je pourrais essayer d'énumérer tous les cycles du graphe, puis calculer le maximum, mais le nombre total de cycles peut être très grand (si le graphique est terminé alors une séquence de sommets où la première et la dernière sont identiques est un cycle ).

Avez-vous une idée de trouver ce cycle de poids maximal sans tous les cycles énumérer?

Si vous avez besoin hypothèse sur le graphique (des poids-positifs, par exemple) s'il vous plaît les indique.

Answer 1

est NP-dur.

problème hamiltonien cycle peut être réduit à cela.

Etant donné un graphe pour lequel nous devons vérifier s'il existe un cycle hamiltonien ou non, le poids assign 1 à chaque bord.

Maintenant, exécutez votre algorithme pour obtenir le cycle de poids maximal. Si le poids est

Answer 2

Si vous pouvez trouver le chemin pondérée minimum dans votre cas spécifique, juste à inverser les signes de tous les poids et appliquer votre algorithme. Bien sûr, vous faites des hypothèses inexprimées parce que l'argument de Moron est correct (sans jeu de mots). Les hypothèses que vous faites peut être un poids positif ou aucun cycle de poids négatif. Je pense que vous devriez faire un effort pour les exposer au lieu de laisser les gens recherchent dans l'espace infini des hypothèses possibles. En ce qui concerne les résultats de la dureté, c'est aussi difficile de se rapprocher dans un certain nombre de passage, consultez ce document . Le même document contient plusieurs résultats positifs pour les types importants de graphiques, mais il est préoccupé par les chemins les plus longs donc non pondérés je suppose que la plupart des algorithmes dans le document ne sera pas directement l'aide dans votre cas. Si vous recherchez des « cycles lourds », vous trouverez un certain nombre de documents intéressants, mais ils sont plus un caractère mathématique. Si votre poids sont de petits entiers (jusqu'à un polynôme de la taille du graphique), vous pouvez essayer de remplacer chaque bord avec un chemin non pondérée pour réduire votre problème au cas non pondéré. J'espère que cela aide à un certain degré, mais vous pourriez avoir un problème de recherche ouvert sur vos mains.