| dbo:abstract
|
- En mathématiques, dans le cadre de la théorie des graphes, un chemin hamiltonien d'un graphe orienté ou non orienté est un chemin qui passe par tous les sommets une fois et une seule. Un cycle hamiltonien est un chemin hamiltonien qui est un cycle. Un graphe hamiltonien est un graphe qui possède un cycle hamiltonien. Un graphe hamiltonien ne doit pas être confondu avec un graphe eulérien, où l'on passe par toutes les arêtes une fois et une seule : dans un cycle hamiltonien, on peut très bien négliger de passer par certaines arêtes. Un graphe peut être eulérien, hamiltonien, les deux à la fois, ou aucun des deux : le graphe papillon est un exemple de graphe eulérien mais pas hamiltonien. Un graphe hamiltonien peut contenir plusieurs cycles hamiltoniens : ainsi, le graphe de Chvátal a 12 sommets, 24 arêtes et 370 cycles hamiltoniens distincts. On a démontré un certain nombre de conditions mathématiques, qui, si elles sont vérifiées, permettent d'assurer qu'un graphe est hamiltonien, ainsi que des conditions qui, si elles ne sont pas vérifiées, assurent qu'il ne l'est pas. On peut par ailleurs confier à des ordinateurs le soin de chercher des cycles hamiltoniens au moyen d'algorithmes que l'on a optimisés petit à petit. Dans les deux cas, le problème algorithmique du chemin hamiltonien est NP-complet, i.e. difficile à résoudre dans un temps raisonnable dans le cas général. Les graphes hamiltoniens sont un domaine de recherche actif à la fois en mathématiques et en informatique. (fr)
- En mathématiques, dans le cadre de la théorie des graphes, un chemin hamiltonien d'un graphe orienté ou non orienté est un chemin qui passe par tous les sommets une fois et une seule. Un cycle hamiltonien est un chemin hamiltonien qui est un cycle. Un graphe hamiltonien est un graphe qui possède un cycle hamiltonien. Un graphe hamiltonien ne doit pas être confondu avec un graphe eulérien, où l'on passe par toutes les arêtes une fois et une seule : dans un cycle hamiltonien, on peut très bien négliger de passer par certaines arêtes. Un graphe peut être eulérien, hamiltonien, les deux à la fois, ou aucun des deux : le graphe papillon est un exemple de graphe eulérien mais pas hamiltonien. Un graphe hamiltonien peut contenir plusieurs cycles hamiltoniens : ainsi, le graphe de Chvátal a 12 sommets, 24 arêtes et 370 cycles hamiltoniens distincts. On a démontré un certain nombre de conditions mathématiques, qui, si elles sont vérifiées, permettent d'assurer qu'un graphe est hamiltonien, ainsi que des conditions qui, si elles ne sont pas vérifiées, assurent qu'il ne l'est pas. On peut par ailleurs confier à des ordinateurs le soin de chercher des cycles hamiltoniens au moyen d'algorithmes que l'on a optimisés petit à petit. Dans les deux cas, le problème algorithmique du chemin hamiltonien est NP-complet, i.e. difficile à résoudre dans un temps raisonnable dans le cas général. Les graphes hamiltoniens sont un domaine de recherche actif à la fois en mathématiques et en informatique. (fr)
|
| rdfs:comment
|
- En mathématiques, dans le cadre de la théorie des graphes, un chemin hamiltonien d'un graphe orienté ou non orienté est un chemin qui passe par tous les sommets une fois et une seule. Un cycle hamiltonien est un chemin hamiltonien qui est un cycle. Un graphe hamiltonien est un graphe qui possède un cycle hamiltonien. Un graphe hamiltonien peut contenir plusieurs cycles hamiltoniens : ainsi, le graphe de Chvátal a 12 sommets, 24 arêtes et 370 cycles hamiltoniens distincts. (fr)
- En mathématiques, dans le cadre de la théorie des graphes, un chemin hamiltonien d'un graphe orienté ou non orienté est un chemin qui passe par tous les sommets une fois et une seule. Un cycle hamiltonien est un chemin hamiltonien qui est un cycle. Un graphe hamiltonien est un graphe qui possède un cycle hamiltonien. Un graphe hamiltonien peut contenir plusieurs cycles hamiltoniens : ainsi, le graphe de Chvátal a 12 sommets, 24 arêtes et 370 cycles hamiltoniens distincts. (fr)
|
