Wikipédia

Théorème de Fleischner

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 carré (en) 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.

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

Définitions et énoncé modifier

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 2 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 :

Théorème de Fleischner — Le carré d'un graphe fini biconnexe avec au moins trois sommets est hamiltonien.

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 modifier

Dans le théorème de Fleischner, on peut contraindre le cycle hamiltonien de G 2 à 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[1].

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)[2] . Il est également un graphe pancyclique, ce qui signifie que pour chaque sommet v et tout entier k avec  , il existe un cycle de longueur k contenant v[3].

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[4].

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 2 a un chemin hamiltonien doublement infini[5]. Plus généralement, si G est localement fini, biconnex et a un nombre quelconque de bouts, alors G 2 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 modifier

Le cycle hamiltonien dans carré d'un graphe biconnexe à n sommet peut être trouvé en temps linéaire[6], ce résultat datant de 2018 améliore la première solution algorithmique de Lau en temps d'exécution O (n 2 )[7]. 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[8].

Historique modifier

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[9]. 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 »[10]

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[11]. Des contre-exemples à cette conjecture ont été découverts plus tard, [12] 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 [13], a été donnée par (Říha 1991)[14], et une autre démonstration simplifiée du théorème a été donnée par Georgakopoulos en 2009[15]'[16]'[17].

Notes et références modifier

Notes modifier

  1. ↑ (Fleischner 1976); (Müttel et Rautenbach 2012).
  2. ↑ (Chartrand et al. 1974); (Chartrand, Lesniak et Zhang 2010)
  3. ↑ (Hobbs 1976), en réponse à une conjecture de (Bondy 1971).
  4. ↑ (Underground 1978); (Bondy 1995).
  5. ↑ Thomassen (1978).
  6. ↑ (Alstrup, Georgakopoulos, Rotenberg, Thomassen 2018)
  7. ↑ (Lau 1980); (Parker et Rardin 1984).
  8. ↑ (Parker et Rardin 1984); (Hochbaum et Shmoys 1986).
  9. ↑ (Fleischner 1974). Pour des conjectures antérieures, voir Fleischner and (Chartrand, Lesniak et Zhang 2010).
  10. ↑ Compte-rendu sur MathReviews : lien Math Reviews
  11. ↑ (Chvátal 1973); (Bondy 1995).
  12. ↑ Bauer, Broersma et Veldman (2000).
  13. ↑ Chartrand et al. (1974).
  14. ↑ (Bondy 1995); (Chartrand, Lesniak et Zhang 2010).
  15. ↑ Georgakopoulos (2009a).
  16. ↑ Chartrand, Lesniak et Zhang (2010).
  17. ↑ Diestel (2012).

Articles modifier

Ouvrages généraux modifier

Ce document provient de « https://fr.wikipedia.org/w/index.php?title=Théorème_de_Fleischner&oldid=195102981 ».