Grafo dual

Archiu:Duals graphs.svg

El grafo G és dual del G', i viceversa.

En teoria de grafos, un grafo dual G' d'un grafo planar G és un grafo que té un vèrtiç per cada regió de G, i una aresta per cada aresta en G unint a dos regions veïnes.

Propietats

Archiu:Noniso dual graphs.svg

G' i G″ són duals de G, pero no isomorfos.

• Si G' és el grafo dual d'un grafo planar G, llavors G' també és un grafo planar (que pot tindre bucles i ser un multigrafo, és dir, tindre arestes múltiples).
• Si G és un grafo planar, llavors pot ser que no existixca un únic grafo dual per a G, en el sentit que G pot tindre grafos duals no-isomorfos, depenent de la distribució particular dels plans. En la figura, G′ i G″ no són isomorfos perque G′ té un nodo en grau 6 (la regió exterior) que G″ no té (vore diagrama).

Una propietat molt important és la següent:

• Un grafo $G$ és isomorfo al dual del seu dual, que denotarem per $G^{″}:=(G^{\prime }{)}^{\prime }$.

Açò permet demostrar atres propietats com, per eixemple,

• Si un grafo planar és euleriano, el seu grafo dual és bipartito.

Grafo autodual

Un grafo autodual és aquell que és isomorfo al seu dual.

Propietats

Sean dos grafos planars G=(V,I) i G'=(V',I'), els conjunts de la qual de regions són R i R' , respectivament, llavors:

• |I'| = |I|
• |V'| = |R|
• |R'| = |V|

Referències

• H. Whitney, Senar-separable and planar graphs, Trans. Amer. Math. Soc. 34 (1932), 339–362.