Graphe dual
Un article de Wikipédia, l'encyclopédie libre.
 |
Cet article est une ébauche à compléter concernant les mathématiques, vous pouvez partager vos connaissances en le modifiant. |
Étant donné un graphe 
, où 
est un ensemble de sommets quelconque, et l'ensemble d'arêtes 
est une relation binaire sur , c'est-à-dire un sous ensemble de 
, le graphe dual de 
a pour ensemble de sommets et pour ensemble d'arêtes
Cela signifie que 
et 
sont reliées entre-elles si et seulement si elles avaient un somment commun dans le premier graphe (elle étaient adjacentes). Pour simplifier on suppose ici que le graphe n'est pas orienté, c'est-à-dire que la relation E est symétrique.
On peut remarquer quelques propriétés
- Le graphe dual d'un polygone est un polygone de même degré, donc isomorphe.
- Le graphe dual du graphe dual de est isomorphe à .
- Le dual d'un graphe planaire est un graphe planaire.
[modifier] Voir aussi
- Dual d'un polyèdre, qui est une généralisation.
- Diagramme de Voronoï, dual de la triangulation de Delaunay.
- Dualité (mathématiques)
|
Portail des mathématiques – Accédez aux articles de Wikipédia concernant les mathématiques. |
