Théorème de Fleischner

Un graphe biconnexe, son carré et un cycle hamiltonien dans le carré.

En théorie des graphes, le théorème de Fleischner donne une condition suffisante pour qu'un graphe contienne un cycle hamiltonien. Il dit que le Modèle:Lien d'un graphe biconnexe est un graphe hamiltonien. Le théorème porte le nom de Herbert Fleischner, qui en a publié la preuve en 1974.

Définitions et énoncé

Un graphe non orienté G est hamiltonien s'il contient un cycle qui passe par chacun de ses sommets exactement une fois. Il est 2-connexe (ou biconnexe) s'il ne possède pas de point d'articulation, un sommet dont la suppression déconnecte le graphe. Tous les graphes biconnexes ne sont pas hamiltoniens : des contre-exemples sont par exemple le graphe de Petersen et le graphe biparti complet K _2,3 .

Le carré de G est un graphe G ² qui a le même ensemble de sommets que G, et dans lequel deux sommets sont adjacents si et seulement s'ils ont une distance d'au plus deux dans G. Le théorème de Fleischner est : Modèle:Théorème De manière équivalente, les sommets de chaque graphe biconnexe G peuvent être ordonnés cycliquement de telle sorte que les sommets adjacents dans cet ordre soient à une distance d'au plus deux les uns des autres dans G.

Extensions

Dans le théorème de Fleischner, on peut contraindre le cycle hamiltonien de G ² à ce que pour deux sommets donnés v et w de G il contienne deux arêtes de G incidentes à v et une arête de G incidente à w . De plus, si v et w sont adjacents dans G, alors ce sont trois arêtes différentes de G.

En plus d'avoir un cycle hamiltonien, le carré d'un graphe G biconnexe est également connexe au sens hamiltonien (ce qui signifie qu'il possède chemin hamiltonien commençant et se terminant en deux sommets spécifiés) et être 1-hamiltonien (ce qui signifie que si un sommet est supprimé, le graphe restant possède encore un cycle hamiltonien) . Il est également un graphe pancyclique, ce qui signifie que pour chaque sommet v et tout entier k avec $3\le k\le |V(G)|$, il existe un cycle de longueur k contenant v.

Si un graphe G n'est pas biconnexe, alors son carré peut ou non avoir un cycle hamiltonien, et déterminer s'il en a un est NP-complet.

Un graphe infini ne peut pas avoir un cycle hamiltonien, car chaque cycle est fini, mais Carsten Thomassen a prouvé que si G est un graphe biconnexe localement fini avec une seule bout, alors G ² a un chemin hamiltonien doublement infiniModèle:Sfnp. Plus généralement, si G est localement fini, biconnex et a un nombre quelconque de bouts, alors G ² a un cercle hamiltonien. Dans un espace topologique compact obtenu en considérant le graphe comme un complexe simplicial et en ajoutant un point supplémentaire à l'infini à chacune de ses bouts, un cercle hamiltonien est défini comme un sous-espace homéomorphe à un cercle euclidien qui couvre chaque sommet.

Algorithmes

Le cycle hamiltonien dans carré d'un graphe biconnexe à n sommet peut être trouvé en temps linéaire, ce résultat datant de 2018 améliore la première solution algorithmique de Lau en temps d'exécution O (n ² ). Le théorème de Fleischner peut être utilisé pour fournir une 2-approximation du problème de goulot d'étranglement du voyageur de commerce dans les espaces métriques.

Historique

Une preuve du théorème de Fleischner a été annoncée par Herbert Fleischner en 1971 et publiée par lui en 1974, résolvant ainsi une conjecture de 1966 de Crispin Nash-Williams, énoncée également indépendamment par L. W. Beineke et Michael D. Plummer. Dans son compte-rendu de l'article de Fleischner, Nash-Williams écrit que celui-ci avait résolu « un problème bien connu qui a résisté pendant plusieurs années l'ingéniosité d'autres théoriciens des graphes »

La preuve originale de Fleischner était compliquée. Václav Chvátal, dans l'article où il introduit la ténacité graphique, observe que le carré d'un graphe k-sommet-connexe est nécessairement k-dur; il conjectura que les graphes 2-durs sont hamiltoniens, ce qui aurait donné une autre preuve du théorème de Fleischner. Des contre-exemples à cette conjecture ont été découverts plus tard, Modèle:Sfnp mais la possibilité qu'une borne finie sur la dureté pourrait impliquer le caractère hamiltonien reste un problème ouvert important dans la théorie des graphes. Une preuve plus simple, à la fois du théorème de Fleischner et de ses extensions par Modèle:Sfnp, a été donnée par Modèle:Harv, et une autre démonstration simplifiée du théorème a été donnée par Georgakopoulos en 2009Modèle:SfnpModèle:'Modèle:SfnpModèle:'Modèle:Sfnp.

Notes et références

Articles

• Modèle:Article
• Modèle:Article.
• Modèle:Article.
• Modèle:Article.
• Modèle:Article.
• Modèle:Article.
• Modèle:Article.
• Modèle:Article.
• Modèle:Article.
• Modèle:Article.
• Modèle:Article.
• Modèle:Ouvrage. Cité par Modèle:Harv.
• Modèle:Article.
• Modèle:Article.
• Modèle:Article.
• Modèle:Article.
• Modèle:Article.

Ouvrages généraux

• Modèle:Ouvrage.
• Modèle:Ouvrage.
• Modèle:Ouvrage