Grafo dual

Summary

En teoría de grafos, un grafo dual G' de un grafo planar G es un grafo que tiene un vértice por cada región de G, y una arista por cada arista en G uniendo a dos regiones vecinas.

El grafo G es dual del G', y viceversa.

Propiedades editar

 
G' y G″ son duales de G, pero no isomorfos.
  • Si G' es el grafo dual de un grafo planar G, entonces G' también es un grafo planar (que puede tener bucles y ser un multigrafo, es decir, tener aristas múltiples).
  • Si G es un grafo planar, entonces puede que no exista un único grafo dual para G, en el sentido que G puede tener grafos duales no-isomorfos, dependiendo de la distribución particular de los planos. En la figura, G′ y G″ no son isomorfos porque G′ tiene un nodo con grado 6 (la región exterior) que G″ no tiene (ver diagrama).

Una propiedad muy importante es la siguiente:

  • Un grafo   es isomorfo al dual de su dual, que denotaremos por  .
Demostración
Queremos, en primer lugar, construir una biyección  . Luego veremos que conserva la adyacencia. Dado un grafo  , dentro de cada cara de   hay exactamente un vértice de  .

En efecto, podemos representar   poniendo el vértice   de   dentro de la correspondiente cara   de   y dibujando una arista   de   que se corresponda con una arista   de   de forma que interseque a   exactamente una vez y que no interseque ninguna otra arista de   (ver dibujos de la derecha). Podemos ahora utilizar el teorema de la curva de Jordan para acabar de demostrar la anterior afirmación.

Esto nos da una biyección entre vértices de   y caras de  . Ahora, dada una cara de  , esta está representada por un único vértice de   por definición. Esto nos da una biyección entre   y  . Componiendo ambas biyecciones tenemos una biyección  .

Veamos que esta biyección conserva la adyacencia. Dos vértices   de   son vecinos en   si y sólo si sus caras correspondientes   de   son contiguas. Equivalentemente, los vértices   de   correspondientes a las caras   de   son vecinos. Por tanto, la adyacencia se conserva y tenemos pues un isomorfismo, como queríamos.  

Esto permite demostrar otras propiedades como, por ejemplo,

Demostración
En efecto, supongamos que   no es bipartito y llegaremos a contradicción. Olvidémonos por ahora del hecho de que   es el dual de   y considerémoslo como un grafo en sí mismo.

Como   no es bipartito, debe tener un ciclo de orden impar, pues si no lo tuviera sería bipartito. Consideremos ahora la representación de ese ciclo de orden impar. Una de las caras en su interior debe tener un número impar de aristas, pues si no el ciclo sería de orden par. Esa cara será un vértice de grado impar del grafo  , por lo que   no es euleriano.

Pero, por la propiedad anterior,   es isomorfo a  , por lo que   tampoco es euleriano, lo que es una contradicción.  

Grafo autodual editar

Un grafo autodual es aquel que es isomorfo a su dual.

Propiedades editar

Sean dos grafos planares G=(V,E) y G'=(V',E'), cuyos conjuntos de regiones son R y R' , respectivamente, entonces:

  • |E'| = |E|
  • |V'| = |R|
  • |R'| = |V|

Referencias editar

  • H. Whitney, Non-separable and planar graphs, Trans. Amer. Math. Soc. 34 (1932), 339–362.
  •   Datos: Q2294516
  •   Multimedia: Dual graphs / Q2294516