Graphe autodual
En théorie des graphes, un graphe autodual est son propre graphe dual[1].
Le graphe dual d'un graphe G est défini à partir d'un plongement de G sur une surface. À partir d'un tel plongement, on peut définir les faces de G. Le graphe dual de G est alors le graphe dont les sommets correspondent aux faces de G et où deux sommets sont adjacents s'ils correspondent à deux faces adjacentes. La notion est souvent limitée aux graphes planaires mais existe aussi pour les graphes graphes toriques ou pour tout autre plongement dans une surface de genre supérieur.
Le dual d'un graphe n'est pas nécessairement unique mais peut dépendre du plongement choisi et du genre de la surface choisie.
La surface considérée pour le plongement d'un graphe doit toujours être du même genre que le graphe. Ainsi seuls les plongements sur le plan seront considérés pour les graphes planaires (de genre 0) et seuls les plongements sur le tore seront considérés pour les graphes de genre 1[2].
Quand on parle d'un graphe autodual c'est soit qu'il dispose d'un plongement privilégié ou unique, soit que tous ses plongements donnent un dual qui lui soit isomorphe, soit que le plongement est précisé.
Propriétés
- Le squelette d'un polyèdre autodual forme un graphe planaire autodual. Ainsi le graphe graphe tétraédrique est planaire et autodual.
- Il existe une infinité de graphes autoduaux. Par exemple, le graphe roue Wn est planaire et autodual pour tout n.
- Le dual d'un graphe étant nécessairement un graphe connexe, un graphe autodual est toujours un connexe.
Références
- (en) Eric W. Weisstein, Self-Dual Graph (MathWorld)
- Alan Bruce Hill, « Self-Dual Graphs », Thesis for the degree of Master of Mathematics, University of Waterloo, Ontario, Canada, 2002. etd.uwaterloo.ca