Voyageur de commerce

Soit $G$ un graphe (orienté ou non) valué par une fonction $c$, le poids d'une chemin (ou d'un circuit) $K$ la somme, pour toute arête $a$ de $K$, des $c(a)$.

• données : un graphe $G$
• question : trouver un circuit hamiltonien de poids minimal dans $G$.

Ce problème est NP-Complet.