Grafo dual

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.

Propiedades

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 $G$ es isomorfo al dual de su dual, que denotaremos por $G'':=(G')'$ .

Demostración
Queremos, en primer lugar, construir una biyección $G\leftrightarrow G''$ . Luego veremos que conserva la adyacencia. Dado un grafo $G$ , dentro de cada cara de $G'$ hay exactamente un vértice de $G$ . En efecto, podemos representar $G'$ poniendo el vértice $v_{f}'$ de $G'$ dentro de la correspondiente cara $f$ de $G$ y dibujando una arista $e'$ de $G'$ que se corresponda con una arista $e$ de $G$ de forma que interseque a $e$ exactamente una vez y que no interseque ninguna otra arista de $G$ (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 $G$ y caras de $G'$ . Ahora, dada una cara de $G'$ , esta está representada por un único vértice de $G''$ por definición. Esto nos da una biyección entre $G'$ y $G''$ . Componiendo ambas biyecciones tenemos una biyección $G\leftrightarrow G''$ . Veamos que esta biyección conserva la adyacencia. Dos vértices $u,v$ de $G$ son vecinos en $G$ si y sólo si sus caras correspondientes $f_{u}',f_{v}'$ de $G'$ son contiguas. Equivalentemente, los vértices $u'',v''$ de $G''$ correspondientes a las caras $f_{u}',f_{v}'$ de $G'$ son vecinos. Por tanto, la adyacencia se conserva y tenemos pues un isomorfismo, como queríamos. $\quad \square$

Esto permite demostrar otras propiedades como, por ejemplo,

Si un grafo planar es euleriano, su grafo dual es bipartito.

Demostración
En efecto, supongamos que $G'$ no es bipartito y llegaremos a contradicción. Olvidémonos por ahora del hecho de que $G'$ es el dual de $G$ y considerémoslo como un grafo en sí mismo. Como $G'$ 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 $G''$ , por lo que $G''$ no es euleriano. Pero, por la propiedad anterior, $G''$ es isomorfo a $G$ , por lo que $G$ tampoco es euleriano, lo que es una contradicción. $\quad \square$

Grafo autodual

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

Propiedades

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

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

Datos: Q2294516
Multimedia: Dual graphs / Q2294516