Proyecto #5 Detección de Planaridad

Bueno amigos en este proyecto 5 a mi me corresponde presentar el tema detección de planaridad, espero les guste el tema.


PLANARIDAD
Una gráfica puede pensarse como un diagrama que consiste de una colección de puntos y líneas que se unen entre sí. Esta idea puede caracterizarse definiendo a cualquier gráfica G como un par de conjuntos (V(G),E(G)) donde V(G) es un conjunto finito no vacío de elementos llamados vértices y E(G) es un conjunto finito de pares no ordenados de elementos de V(G) llamados líneas o aristas.

A continuación presentamos dos ejemplos de gráficas que si bien parecen bastante diferentes a primera vista son esencialmente iguales (isomorfas).

En la gráfica de La figura 1 hay dos aristas que se intersectan en un punto que no es un vértice de ésta, mientras que en la segunda gráfica las aristas no se intersectan más que en un vértice. Es de notarse que a pesar de que dos gráficas puedan parecer tan distintas posean la misma estructura; observemos que ambas tienen el mismo conjunto de puntos y vértices, es decir, son la “misma” gráfica pero dibujada de diferente manera.


Ahora, dependiendo de cómo dibujemos una gráfica, ésta puede ser plana si puede ser dibujada en el plano de manera que sus aristas no se intersecten geométricamente mas que en un vértice. Por ejemplo, en la figura anterior tenemos dos formas de dibujar la misma gráfica: en la primera el dibujo no es una gráfica plana, mientras que en la segunda si.

Cuando una gráfica es plana, es decir, que podemos dibujarla en el plano sin que sus aristas se intersecten, entonces todos los puntos del plano que no están en G forman caras o regiones. El número r de dichas caras o regiones está dado por la fórmula de Euler como se puede ver en los siguientes resultados.

Teorema 1 Sea G una gráfica conexa (es decir, existe una trayectoria entre cualesquiera dos vértices) plana con p vértices y q aristas y r caras o regiones y con p=3 entonces p-q+r=2.
De donde se puede inferir que:
Corolario 1 Si G es una gráfica plana con p vértices y q aristas y r regiones,
entonces p-q+r=1+k(G) donde k(G) es el número de componentes conexas
de G.

Por otro lado, una gráfica plana puede tener la singularidad de que si agregamos una arista ésta intersecta necesariamente a otra arista, es decir, si para todo u, v que pertenecen al conjunto de vértices V(G) tales que u y v no son adyacentes entonces G+uv no es plana.

Este tipo de gráficas se llama maximal y en su caso las regiones están limitadas por un triángulo, debido a lo cual a las gráficas planas maximales también se les suele llamar triangulaciones.

El hecho que una gráfica sea plana esta relacionado con el número de aristas que ésta tiene, si una gráfica tiene pocas aristas es muy probable que esta sea plana, por el contrario si tiene muchas aristas hay más probabilidades de que no sea plana.
Los siguientes resultados nos permiten calcular el número máximo de aristas que puede
tener una gráfica plana.
Aquí les dejo la presentación en Power Point:

Proyecto 5 algcomp

View more presentations from erik.

">PRESENTACIÓN

JUEGO

Recalco que este proyecto no sería posible si no fuera por las siguientes fuentes consultadas.

fuentes
1
2
3