Dualité

Une autre notion importante en théorie des graphes est la notion de dualité. Soit un graphe planaire et une représentation planaire de ce graphe. L'ensemble des arêtes partitionne le plan dans une famille , au plus dénombrable, de régions connexes, appelées faces du graphe ; elles sont de domaines du plan dont les bords sont les arêtes. La figure suivante montre les trois faces d'un graphe planaire

unit=5mm (8,7) (5mm,5mm) (3,2)(5,2)(5,4)(4,6)(3,4)(5,4)(7,5) (3,2)(3,4) (1.5,3)a (4,3)b (4,4.5)c

À la représentation du graphe, on va associer son dual par construction explicite d'une bijection qui

• à chaque face de fait correspondre un sommet de et
• à chaque arête de fait correspondre une arête de .

La correspondance est ainsi définie que

• si l'arête sépare deux faces et , alors l'arête rélie les sommets et
• si l'arête est entourée d'une face (c'est-à-dire est incidente à un sommet de degré 1) alors est une 1-boucle incidente à (c'est-à-dire ).

Le dual du graphe précédent est construit dans la figure ci-dessous

unit=5mm (8,7) (5mm,5mm) (3,2)(5,2)(5,4)(4,6)(3,4)(5,4)(7,5) (3,2)(3,4) -(1,3.8)(4,14)(10,-7)(1,3.8) [br](1,3.8) (1,3.8)(4,3)(4,4.5)(1,3.8) [tl](4,3) [bl](4,4.5)