Graphe hamiltonien
Un article de Wikipédia, l'encyclopédie libre.
Vous avez de  |
Cet article est une ébauche à compléter concernant les mathématiques, vous pouvez partager vos connaissances en le modifiant. |
Un graphe hamiltonien est un graphe possèdant au moins un cycle passant par tous les sommets une et une seule fois. Un tel cycle élémentaire (ne passant pas deux fois par le même sommet) est alors appelé cycle hamiltonien. Un graphe hamiltonien peut contenir plusieurs cycles hamiltoniens.
Trouver un cycle hamiltonien pour un graphe donné est un problème algorithmiquement difficile, relié au problème du voyageur de commerce (cycle hamiltonien d'un graphe complet).
A ne pas confondre avec le graphe eulérien.
|
Portail des mathématiques – Accédez aux articles de Wikipédia concernant les mathématiques. |
