Loading AI tools
De Wikipédia, l'encyclopédie libre
En théorie des graphes, le théorème de Grinberg énonce une condition nécessaire pour qu'un graphe planaire possède un cycle hamiltonien, basée sur les longueurs des cycles de ses faces. Le résultat a été utilisé pour construire des graphes planaires non hamiltoniens avec d'autres propriétés, et pour donner de nouveaux contre-exemples à la conjecture de Tait (elle-même réfutée par W. T. Tutte en 1946). Le théorème a été prouvé par mathématicien letton Emanuel Grinberg en 1968.
Théorème de Grinberg — Soit G un graphe planaire fini possédant un cycle hamiltonien C, plongé dans le plan. Soient et le nombre de faces à k côtés du plongement qui sont respectivement à l'intérieur et à l'extérieur de C . Alors on a :
La démonstration est une conséquence de la formule d'Euler.
Corollaire — Si toutes les faces d'un graphe planaire plongé dans le plan ont un contour de longueur égale à 2 modulo 3, à l'exception d'une seule, alors le graphe n'est pas hamiltonien.
En effet, le facteur dans les contributions des faces dans la formule prise modulo 3 fait qu'elles sont nulles sauf pour la face exceptionnelle unique. Par exemple, pour le graphe de la figure, toutes les faces bornées ont 5 ou 8 côtés, mais la face extérieure a 9 côtés, elle satisfait donc cette condition et le graphe n'est pas hamiltonien. Dans l'exemple donné plus haut, le graphe a avec 46 sommets et 25 faces ; toutes les faces finies ont cinq ou huit arêtes, qui sont toutes deux des nombres qui sont 2 mod 3, et la face infinie a neuf arêtes, qui n'est pas égal à 2 mod 3. Par conséquent, par le corollaire du théorème de Grinberg, le graphe ne peut pas être hamiltonien.
Grinberg a utilisé le théorème pour trouver des graphes polyédriques cubiques non hamiltoniens avec une connectivité d'arête cyclique élevée. La connectivité d'arête cyclique d'un graphe est par définition le plus petit nombre d'arêtes dont la suppression donne un sous-graphe qui a plus d'une composante cyclique. Le graphe de graphe de Tutte à 46 sommets et les plus petits graphes polyédriques cubiques non hamiltoniens qui en sont dérivés ont tous une connectivité d'arête cyclique égale à trois. Grinberg a utilisé son théorème pour trouver un graphe polyédrique cubique non hamiltonien avec 44 sommets, 24 faces et une connectivité d'arête cyclique égale à quatre, et un autre exemple (celui donné dans la figure) avec 46 sommets, 25 faces et une connectivité d'arête cyclique égale à cinq ; c'est la plus grande connectivité d'arête cyclique possible pour un graphe planaire cubique autre que K4.
Le théorème de Grinberg a également été utilisé pour trouver des graphes hypohamiltoniens planaires : ce sont des graphes qui ne sont pas hamiltoniens mais qui peuvent être rendus hamiltoniens en supprimant un seul sommet. La construction fait à nouveau usage de ce que toutes les faces sauf une ont un nombre d'arêtes congruent à 2 mod 3[1],[2]. Thomassen (1981)[3] utilise le théorème d'une manière un peu plus compliquée pour trouver un graphe hypohamiltonien cubique plan : le graphe qu'il construit comprend une face à 4 arêtes adjacente à quatre faces à 7 arêtes, et toutes les autres faces ont cinq ou huit arêtes. Afin de satisfaire le théorème de Grinberg, un cycle hamiltonien devrait séparer l'une des faces à 4 ou 7 arêtes des quatre autres, ce qui n'est pas possible.
Il existe des graphes planaires non hamiltoniens dans lesquels toutes les faces ont cinq ou huit côtés. Pour ces graphes, la formule de Grinberg prise modulo trois est toujours satisfaite par toute partition des faces en deux sous-ensembles, empêchant l'application de son théorème pour prouver la non-hamiltonicité dans ce cas[4].
Il n'est pas possible d'utiliser le théorème de Grinberg pour trouver des contre-exemples à la conjecture de Barnette selon laquelle tout graphe biparti polyédrique cubique est hamiltonien. Tout graphe polyédrique bipartite cubique a une partition des faces en deux sous-ensembles satisfaisant le théorème de Grinberg, qu'il possède ou non un cycle hamiltonien[5].
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.
