Graphe médial
From Wikipedia, the free encyclopedia
En théorie des graphes, le graphe médial du graphe planaire G est un graphe M(G) qui représente les adjacences entre les côtés des faces de G. Les graphes médiaux ont été introduits en 1922 par Ernst Steinitz dans l'étude des propriétés combinatoires des polyèdres convexes[1], bien que la construction inverse ait déjà été utilisée par Peter Tait en 1877, dans son étude fondamentale des nœuds et entrelacs [2],[3],[4].
Étant donné un graphe planaire G, son graphe médial M(G) est le graphe dont les sommets sont les arêtes de G, deux sommets étant reliés si les arêtes de G correspondantes sont consécutives dans une de ses faces. Le graphe médial est donc un sous-graphe du line graph L(G).
La notion de graphe médial s'étend aux graphes plongés dans des surfaces de genre quelconque.
Propriétés
- Le graphe médial d'un graphe planaire est lui aussi planaire, et de plus ses sommets sont d'ordre 4 (il est 4-régulier).
- Le graphe médial de G et celui de son dual sont isomorphes. Inversement, pour tout graphe planaire 4-régulier H, il existe exactement deux graphes planaires ayant H pour graphe médial et ces deux graphes sont duaux l'un de l'autre[5].
- Comme le graphe médial est associé à un plongement particulier du graphe G, deux plongements différents peuvent donner naissance à des graphes médiaux non isomorphes. Dans la représentation ci-contre, les deux graphes médiaux rouges ne sont pas isomorphes car les deux sommets à boucles sont reliés par une arête dans l'un, et pas dans l'autre.
- Pour obtenir l'un des deux graphes G dont H est le médial, colorier les faces de H avec deux couleurs, ce qui est possible puisque H est eulérien (et donc le graphe dual de H est biparti). Les sommets de G correspondent aux faces d'une couleur donnée. Ces sommets sont reliés par une arête si les faces correspondantes ont un sommet en commun dans H. Notons que l'exécution de cette construction à l'aide des faces de l'autre couleur que la couleur choisie produit le graphe dual de G.
Applications
Pour un graphe planaire G, le double de la valeur du polynôme de Tutte au point (3,3) est égal à la somme des orientations eulériennes pondérées dans le graphe médial de G, où le poids d'une orientation est entre 2 et le nombre de sommets de l'orientation (c'est-à-dire le nombre de sommets dont les arêtes incidentes sont cycliquement ordonnées «in, out, in out»)[6]. Puisque le polynôme de Tutte est invariant par plongement, ce résultat montre que chaque graphe médial a la même somme des orientations eulériennes pondérées.
