- Graphe dual
-
Pour les articles homonymes, voir Dualité (mathématiques) pour les autres notions de dualité en mathématiques.En théorie des graphes, le graphe dual d'un graphe plongé à l'intérieur d'une surface est défini à l'aide des composantes du complémentaire, reliées par les arêtes du graphe plongé.
Cette construction généralise la notion de dualité d'un polyèdre.
Cependant, un même graphe abstrait peut avoir des graphes duaux non isomorphes en fonction du plongement choisi, même dans le cas de plongements dans le plan.
Un graphe (plongé) isomorphe à son dual est dit autodual.
Sommaire
Construction
G' est le graphe dual de G dans le plan
Étant donné un graphe plongé à l'intérieur d'une surface connexe, chaque composante connexe (cellule) du complémentaire est muni d'un point définissant un sommet du graphe dual. Chaque arête du graphe initial définit une arête du graphe dual reliant les composantes du complémentaire qui la bordent[1]. Ces arêtes du graphe dual peuvent être plongées dans la surface de façon à ce que chacune coupe uniquement l'arête correspondante du graphe initial en un seul point.
Propriété
Un graphe dual est toujours connexe.
Un graphe connexe plongé dans le plan est le dual de son graphe dual (à homotopie près du plongement).
Le graphe dual d'un graphe planaire est planaire également par construction.
Remarque
Un graphe dual peut comporter des boucles et des arêtes multiples même si le graphe initial est planaire et simple.
Exemples
- Le graphe tétraédrique plongé sur le plan est son propre dual (on dit d'un tel graphe qu'il est autodual).
Voir aussi
Liens internes
Références
- (en) Eric W. Weisstein, Dual Graph (MathWorld)
Catégorie :- Concept en théorie des graphes
Wikimedia Foundation. 2010.
