Chemin hamiltonien

Chemin hamiltonien (Redirigé à partir du théorème de Bondy – Hvátal) Aller à la navigation Aller à la recherche Cet article porte sur la nature des chemins hamiltoniens. Pour la question de l'existence d'un chemin ou d'un cycle hamiltonien dans un graphe donné, voir problème de chemin hamiltonien. Un cycle hamiltonien autour d'un réseau de six sommets Dans le domaine mathématique de la théorie des graphes, une voie hamiltonienne (ou chemin traçable) est un chemin dans un graphe non orienté ou orienté qui visite chaque sommet exactement une fois. Un cycle hamiltonien (ou circuit hamiltonien) est un cycle qui visite chaque sommet exactement une fois. Un chemin hamiltonien qui commence et se termine à des sommets adjacents peut être complété en ajoutant une arête supplémentaire pour former un cycle hamiltonien, et la suppression de toute arête d'un cycle hamiltonien produit un chemin hamiltonien. Déterminer si de tels chemins et cycles existent dans les graphiques (le problème du chemin hamiltonien et le problème du cycle hamiltonien) sont NP-complets.

Les chemins et les cycles hamiltoniens portent le nom de William Rowan Hamilton qui a inventé le jeu icosien, maintenant également connu sous le nom de puzzle de Hamilton, qui consiste à trouver un cycle hamiltonien dans le graphe des arêtes du dodécaèdre. Hamilton a résolu ce problème en utilisant le calcul icosien, une structure algébrique basée sur des racines d'unité avec de nombreuses similitudes avec les quaternions (également inventé par Hamilton). Cette solution ne se généralise pas aux graphes arbitraires.

Bien qu'il porte le nom de Hamilton, Les cycles hamiltoniens dans les polyèdres avaient également été étudiés un an plus tôt par Thomas Kirkman, qui, en particulier, a donné un exemple de polyèdre sans cycles hamiltoniens.[1] Même plus tôt, Cycles et chemins hamiltoniens dans le graphe de chevalier de l'échiquier, le tour du chevalier, avait été étudié au 9ème siècle en mathématiques indiennes par Rudrata, et à peu près à la même époque en mathématiques islamiques par al-Adli ar-Rumi. Dans l'Europe du XVIIIe siècle, les tours de chevalier ont été publiés par Abraham de Moivre et Leonhard Euler.[2] Contenu 1 Définitions 2 Exemples 3 Propriétés 4 Bondy – Théorème saisi 5 Existence de cycles hamiltoniens dans les graphes planaires 6 Le polynôme du cycle hamiltonien 7 Voir également 8 Remarques 9 Références 10 Liens externes Définitions Un chemin hamiltonien ou chemin traçable est un chemin qui visite chaque sommet du graphe exactement une fois. Un graphe qui contient un chemin hamiltonien est appelé un graphe traçable. Un graphe est connexe hamiltonien si pour chaque paire de sommets il existe un chemin hamiltonien entre les deux sommets.

Un cycle hamiltonien, Circuit hamiltonien, tour de sommet ou cycle de graphe est un cycle qui visite chaque sommet exactement une fois. Un graphe qui contient un cycle hamiltonien est appelé graphe hamiltonien.

Des notions similaires peuvent être définies pour les graphes orientés, où chaque bord (arc) d'un chemin ou d'un cycle ne peut être tracé que dans une seule direction (c'est à dire., les sommets sont reliés par des flèches et les arêtes tracées "queue à tête").

Une décomposition hamiltonienne est une décomposition d'arête d'un graphe en circuits hamiltoniens.

Un labyrinthe de Hamilton est un type de puzzle logique dans lequel le but est de trouver le cycle hamiltonien unique dans un graphe donné.[3][4] Exemples Projections orthographiques et diagrammes de Schlegel avec des cycles hamiltoniens des sommets des cinq solides platoniques - seul l'octaèdre a un chemin ou un cycle eulérien, en prolongeant son chemin par le pointillé vte Un graphe complet à plus de deux sommets est hamiltonien Tout graphe cyclique est hamiltonien Tout tournoi a un nombre impair de chemins hamiltoniens (C'est le tien 1934) Chaque solide platonique, considéré comme un graphique, est hamiltonien[5] Le graphe de Cayley d'un groupe de Coxeter fini est hamiltonien (Pour plus d'informations sur les chemins hamiltoniens dans les graphes de Cayley, voir la conjecture de Lovász.) Les graphes de Cayley sur les groupes nilpotents avec sous-groupe de commutateur cyclique sont hamiltoniens.[6] Le flip graph d'un polygone convexe ou de manière équivalente, le graphe de rotation des arbres binaires, est hamiltonien.[7][8] Propriétés Le graphe de Herschel est le plus petit graphe polyédrique possible qui n'a pas de cycle hamiltonien. Un chemin hamiltonien possible est montré.

Tout cycle hamiltonien peut être converti en un chemin hamiltonien en supprimant l'un de ses bords, mais un chemin hamiltonien ne peut être étendu au cycle hamiltonien que si ses extrémités sont adjacentes.

Tous les graphes hamiltoniens sont biconnectés, mais un graphe biconnecté n'a pas besoin d'être hamiltonien (voir, par exemple, le graphique de Petersen).[9] Un graphe eulérien G (un graphe connexe dont chaque sommet est de degré pair) a forcément un tour d'Euler, une marche fermée passant par chaque arête de G exactement une fois. Ce tour correspond à un cycle hamiltonien dans le graphe linéaire L(g), donc le graphe linéaire de chaque graphe eulérien est hamiltonien. Les graphiques linéaires peuvent avoir d'autres cycles hamiltoniens qui ne correspondent pas aux tours d'Euler, et en particulier le graphe linéaire L(g) de tout graphe hamiltonien G est lui-même hamiltonien, que le graphe G soit ou non eulérien.[10] Un tournoi (avec plus de deux sommets) est hamiltonien si et seulement s'il est fortement connexe.

Le nombre de cycles hamiltoniens différents dans un graphe non orienté complet sur n sommets est (n- 1)! / 2 et dans un graphe orienté complet sur n sommets est (n- 1)!. Ces comptages supposent que les cycles qui sont identiques à part leur point de départ ne sont pas comptés séparément.

Théorème de Bondy – Chvátal La meilleure caractérisation du degré de sommet des graphes hamiltoniens a été fournie dans 1972 par le Bondy–Prenez le théorème, qui généralise les résultats précédents par G. UN. Dirac (1952) et Øystein Ore. Les théorèmes de Dirac et d'Ore peuvent également être dérivés du théorème de Pósa (1962). L'hamiltonicité a été largement étudiée en relation avec divers paramètres tels que la densité du graphe, dureté, sous-graphes interdits et distance entre autres paramètres.[11] Les théorèmes de Dirac et Ore stipulent essentiellement qu'un graphe est hamiltonien s'il a suffisamment d'arêtes.

Le théorème de Bondy-Chvátal opère sur la clôture cl(g) d'un graphe G à n sommets, obtenu en ajoutant à plusieurs reprises une nouvelle arête uv reliant une paire non adjacente de sommets u et v avec deg(v) + degré(tu) ≥ n jusqu'à ce qu'il n'y ait plus de paires avec cette propriété.

Bondy – saisi par le théorème (1976) — Un graphe est hamiltonien si et seulement si sa clôture est hamiltonienne.

Comme les graphes complets sont hamiltoniens, tous les graphes dont la fermeture est complète sont hamiltoniens, qui est le contenu des théorèmes antérieurs suivants de Dirac et Ore.

Théorème de Dirac (1952) — Un graphe simple à n sommets ( {style d'affichage ngeq 3} ) est hamiltonien si chaque sommet a un degré {style d'affichage {tfrac {n}{2}}} ou plus grand.

Théorème de minerai (1960) — Un graphe simple à n sommets ( {style d'affichage ngeq 3} ) est hamiltonien si, pour chaque paire de sommets non adjacents, la somme de leurs degrés est n ou plus.

Les théorèmes suivants peuvent être considérés comme des versions dirigées: Ghouila–Houiri (1960) — Un graphe orienté simple fortement connexe à n sommets est hamiltonien si chaque sommet a un degré entier supérieur ou égal à n.

Meiniel (1973) — Un graphe orienté simple fortement connexe à n sommets est hamiltonien si la somme des degrés complets de chaque paire de sommets distincts non adjacents est supérieure ou égale à {style d'affichage 2n-1} Le nombre de sommets doit être doublé car chaque arête non orientée correspond à deux arcs orientés et donc le degré d'un sommet dans le graphe orienté est le double du degré dans le graphe non orienté.

Rahman-Kaykobad (2005) — Un graphe simple à n sommets admet un chemin hamiltonien si, pour chaque paire de sommets non adjacents, la somme de leurs degrés et de leur plus courte longueur de chemin est supérieure à n.[12] Le théorème ci-dessus ne peut reconnaître l'existence d'un chemin hamiltonien dans un graphe et non un cycle hamiltonien.

Beaucoup de ces résultats ont des analogues pour les graphes bipartis équilibrés, dans lequel les degrés de sommet sont comparés au nombre de sommets d'un seul côté de la bipartition plutôt qu'au nombre de sommets dans l'ensemble du graphe.[13] Existence de cycles hamiltoniens dans les graphes planaires Théorème — Une triangulation planaire 4-connexe a un cycle hamiltonien.[14] Théorème — Un graphe planaire 4-connexe a un cycle hamiltonien.[15] Le polynôme du cycle hamiltonien Une représentation algébrique des cycles hamiltoniens d'un digraphe pondéré donné (dont les arcs sont pondérés à partir d'un certain champ au sol) est le polynôme de cycle hamiltonien de sa matrice de contiguïté pondérée définie comme la somme des produits des poids d'arc des cycles hamiltoniens du digraphe. Ce polynôme n'est pas identiquement nul en fonction des poids de l'arc si et seulement si le digraphe est hamiltonien. La relation entre les complexités computationnelles de son calcul et le calcul du permanent a été montrée par Grigoriy Kogan.[16] Voir aussi la conjecture de Barnette, un problème ouvert sur l'hamiltonicité des graphes polyédriques bipartis cubiques chemin eulérien, un chemin passant par toutes les arêtes d'un graphe théorème de Fleischner, sur les carrés hamiltoniens des graphes Code Gray Théorème de Grinberg donnant une condition nécessaire pour que les graphes planaires aient un cycle hamiltonien Problème de chemin hamiltonien, le problème informatique de la recherche de chemins hamiltoniens graphe hypohamiltonien, un graphe non hamiltonien dans lequel chaque sous-graphe à sommet supprimé est le tour de Hamiltonian Knight, un cycle hamiltonien dans le graphe de chevalier Notation LCF pour les graphes cubiques hamiltoniens. Conjecture de Lovász selon laquelle les graphes vertex-transitifs sont un graphe pancyclique hamiltonien, graphes avec des cycles de toutes longueurs dont un cycle hamiltonien Sept ponts de Königsberg Exposant de la brièveté, une mesure numérique de la distance par rapport à l'hamiltonien que les graphiques d'une famille peuvent être Snake-in-the-box, le plus long chemin induit dans un hypercube Algorithme de Steinhaus – Johnson – Trotter pour trouver un chemin hamiltonien dans un graphe sous-hamiltonien permutoèdre, un sous-graphe d'un graphe hamiltonien plan conjecture de Tait (maintenant connu faux) que les graphes polyédriques 3-réguliers sont hamiltoniens Problème du voyageur de commerce Notes ^ Biggs, N. L. (1981), "J. P. Kirkman, mathématicien", Le Bulletin de la London Mathematical Society, 13 (2): 97–120, est ce que je:10.1112/blms/13.2.97, M 0608093. ^ Watkin, Jean J.. (2004), "Chapitre 2: Tours de chevalier", À tous les niveaux: Les mathématiques des problèmes d'échiquier, Presse de l'Université de Princeton, pp. 25–38, ISBN 978-0-691-15498-5. ^ le cavalier, Johan (2017). Hamilton Mazes - Le guide du débutant. ^ Fridmann, Érich (2009). "Labyrinthes hamiltoniens". Le palais des puzzles d'Erich. Archivé de l'original sur 16 Avril 2016. Récupéré 27 Peut 2017. ^ Gardner, M. "Jeux mathématiques: À propos de la similitude remarquable entre le jeu Icosian et les tours de Hanoï." SCI. Amer. 196, 150–156, Peut 1957 ^ Ghaderpour, E.; Morris, ré. O. (2014). "Les graphes de Cayley sur les groupes nilpotents avec sous-groupe de commutateur cyclique sont hamiltoniens". Ars Mathematica contemporain. 7 (1): 55–72. arXiv:1111.6216. est ce que je:10.26493/1855-3974.280.8d3. ^ Lucas, Jeanne M. (1987), "Le graphe de rotation des arbres binaires est hamiltonien", Journal des algorithmes, 8 (4): 503–535, est ce que je:10.1016/0196-6774(87)90048-4 ^ Hurtado, Ferran; Non, Marc (1999), "Graphe des triangulations d'un polygone convexe et arbre des triangulations", Géométrie computationnelle, 13 (3): 179–188, est ce que je:10.1016/S0925-7721(99)00016-4 ^ Éric Weinstein. "Graphe biconnecté". Wolfram MathWorld. ^ Balakrishnan, R; Ranganathan, K. (2012), "Corollaire 6.5.5", Un manuel de théorie des graphes, Springer, p. 134, ISBN 9781461445296. ^ Gould, Ronald J.. (Juillet 8, 2002). "Avancées sur le problème hamiltonien - Une enquête" (PDF). Université Emory. Récupéré 2012-12-10. ^ Rahman, M. S; Kaykobad, M. (Avril 2005). "Sur les cycles hamiltoniens et les chemins hamiltoniens". Lettres de traitement de l'information. 94: 37–41. est ce que je:10.1016/j.ipl.2004.12.002. ^ Lune, J; Moser, L. (1963), "Sur les graphes bipartis hamiltoniens", Journal israélien de mathématiques, 1 (3): 163–165, est ce que je:10.1007/BF02759704, M 0161332 ^ Whitney, harceleur (1931), "Un théorème sur les graphes", Annales de Mathématiques, Deuxième série, 32 (2): 378–390, est ce que je:10.2307/1968197, JSTOR 1968197, M 1503003 ^ Tous, O. J. (1956), "Un théorème sur les graphes planaires", Trans. Amer. Math. Soc., 82: 99–116, est ce que je:10.1090/s0002-9947-1956-0081471-8 ^ Kogan, Grégory (1996), "Calcul des permanents sur des corps de caractéristique 3: où et pourquoi ça devient difficile", 37e Symposium annuel sur les fondements de l'informatique (FEU '96): 108–114, est ce que je:10.1109/SFCS.1996.548469, ISBN 0-8186-7594-2 Références Bergé, Claude; Ghouila-Houiri, UN. (1962), Programmation, jeux et réseaux de transport, New York: Fils, Inc. DeLeon, Mélisse (2000), "Une étude des conditions suffisantes pour les cycles hamiltoniens" (PDF), Journal de mathématiques de premier cycle Rose-Hulman, 1 (1), archivé de l'original (PDF) sur 2012-12-22, récupéré 2005-11-28. Dirac, g. UN. (1952), "Quelques théorèmes sur les graphes abstraits", Actes de la London Mathematical Society, 3rd Ser., 2: 69–81, est ce que je:10.1112/plms/s3-2.1.69, M 0047308. Hamilton, Guillaume Rowan (1856), "Mémorandum concernant un nouveau système de racines d'unité", Magazine philosophique, 12: 446. Hamilton, Guillaume Rowan (1858), "Compte du calcul icosien", Actes de l'Académie royale d'Irlande, 6: 415–416. Meiniel, M. (1973), "Une condition suffisante d'existence d'un circuit hamiltonien dans un graphe orienté", Journal de théorie combinatoire, Série B, 14 (2): 137–147, est ce que je:10.1016/0095-8956(73)90057-9, M 0317997. Minerai, Øystein (1960), "Remarque sur les circuits de Hamilton", Le mensuel mathématique américain, 67 (1): 55, est ce que je:10.2307/2308928, JSTOR 2308928, M 0118683. Chic, L. (1962), "Un théorème concernant les lignes de Hamilton", Tud hongrois. Décalages. Tapis. Recherche internationale. Comm., 7: 225–226, M 0184876. Weissstein externe gauche, Eric W. "Cycle hamiltonien". MathWorld. Tour Euler et cycles Hamilton Catégories: Problèmes informatiques en théorie des graphesProblèmes NP-completsObjets de la théorie des graphesChemins et cycles hamiltoniensWilliam Rowan Hamilton