Graphe de Halin
# Graphe de Halin

En théorie des graphes, une branche des mathématiques, un graphe de Halin est un graphe planaire construit à partir d'un arbre en reliant toutes ses feuilles dans un cycle qui fait le tour de l'arbre de telle façon que l'arbre reste planaire. On exige de plus que l'arbre comporte au moins quatre sommets et ne comporte pas de sommets de degré 2.

Les graphes de Halin graphs sont nommés d'après le mathématicien allemand Rudolf Halin qui les a étudiés en 1971, mais les graphes de Halin cubiques avaient déjà été étudiés plus d'un siècle auparavant par Thomas Kirkman.

## Exemples

Les graphes roue (les graphes des arêtes d'une pyramide) sont des graphes de Halin ; leur arbre est un graphe étoile.

Le graphe des arêtes d'un prisme triangulaire est également un graphe de Halin (figure).

Le graphe de Frucht, un des plus petits graphes cubiques sans automorphisme de graphe trivial, est aussi un graphe de Halin.

## Propriétés

* Tout graphe de Halin est un graphe planaire au nombre minimal d'arêtes qui est 3-connexe. Le théorème de Steinitz (en) permet d'en déduire que c'est un graphe polyédrique.
* Tout graphe de Halin a un plongement (en) planaire unique, au choix près de l’espace extérieur, c'est-à-dire un unique plongement dans une 2-sphère.
* Tout graphe de Halin est hamiltonien, et chaque arête du graphe appartient à un cycle hamiltonien. De plus, un graphe de Halin reste hamiltonien lorsque l'on supprime n'importe quel sommet.
* Tout graphe de Halin est presque pancyclique, dans le sens où il comporte des cycles de toutes les longueurs de $3$ à $n$ (le nombre de sommets) sauf éventuellement une unique longueur paire. De plus, un graphe de Halin reste presque pancyclique si une seule arête est contractée. Enfin, un graphe de Halin sans sommets intérieurs de degré 3 est pancyclique.
* Tout graphe de Halin a une largeur arborescente inférieure ou égale à 3. Par conséquent, beaucoup de problèmes qui sont NP-complets dans le cas général, comme la recherche d'un stable de taille maximum, peuvent être résolus en durée linéaire dans le cas des graphes de Halin en s'appuyant sur de la programmation dynamique.
* Tout graphe de Halin contient un triangle. En effet, chaque arbre sans sommets de degré 2 contient au moins deux feuilles qui partagent le même parent. En particulier, un graphe de Halin ne peut par être un graphe sans triangle ni un graphe biparti.
* Le dual faible d'un graphe de Halin est biconnexe et planaire extérieur. Un graphe planaire est un graphe de Halin si et seulement si son dual faible est biconnexe et planaire extérieur.

## Historique

En 1971, Halin a introduit les graphes de Halin comme une sorte de graphes au moins 3-connexes, en faisant remarquer que la suppression de n'importe quelle arête du graphe changeait le degré de connexité du graphe. Ces graphes ont gagné en importance lorsque l'on a découvert que de nombreux problèmes algorithmiques qui étaient difficiles à résoudre par calcul pour des graphes planaires arbitraires pouvaient être résolus efficacement avec $eux^,,$ une propriété qui a été expliquée plus tard comme une conséquence de leur faible largeur $arborescente^,.$

Avant les travaux de Halin sur ces graphes, des problèmes d'énumération de graphes (en) concernant les graphes de Halin cubiques ont été étudiés en 1965 par Hans Rademacher. Rademacher définit ces graphes (qu'il appelle based polyhedra, polyèdres à base) comme les graphes polyédriques cubiques dans lesquels une des faces comporte $f-1$ côtés, où $f$ est le nombre de faces du polyèdre. Il mentionne lui-même des travaux bien antérieurs publiés en 1856 par Thomas Kirkman sur la même classe de graphes

Les graphes de Halin sont parfois également appelés roofless polyhedra (polyèdres à ciel ouvert), mais, comme based polyhedra, ce nom peut aussi faire référence aux graphes de Halin cubiques.

