Grafo dual , la enciclopedia libre
![](http://upload.wikimedia.org/wikipedia/commons/thumb/b/ba/Duals_graphs.svg/300px-Duals_graphs.svg.png)
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
[editar]![](http://upload.wikimedia.org/wikipedia/commons/thumb/7/7b/Noniso_dual_graphs.svg/300px-Noniso_dual_graphs.svg.png)
- 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.