miércoles, 19 de mayo de 2010

Proyecto #5

Hola compañeros y profesora, aquí les muestro mi proyecto #5. El tema que elegí fue el de "detección de planaridad".
Este tema es bastante interesante y entretenido ya que ayuda a desarrollar la creatividad a la hora de encontrar alguna solución óptima en cuanto a los grafos, detectar si un grafo es plano o no.

-Definicion del problema
Cuando un grafo o multígrafo se puede dibujar en un plano sin que dos segmentos se corten, se dice que es plano.
Un grafo no es plano si no puede ser dibujado sobre un plano sin que sus aristas se intersequen.

Este problema es de "optimización".
La complejidad asintotica es φ(n)
Aquí les muestro un ejemplo de una pequeña actividad que una vez la profesora nos habia puesto en clases:





El dibujo nos muestra un grafo (figura del cubo) donde podemos apreciar que algunas de sus aristas se intersecan, esto quiere decir que aquel grafo no es plano.
En cambio si el grafo lo modificamos y lo analizamos desde otra perpectiva podemos ver que hay una manera de juntar todas sus aristas sin que estas se intersecan, entonces esto quiere decir que el grafo ahora si es plano.

Ahora les dejare el link de un juego para que se entretengan y comprendan un poco mejor este problema ya que esta basado en este principio.
Juego de las casas y los servicios.
Explicación del juego:


La presentación del juego es la que aparece en la imagen. El objetivo del mismo es conectar cada una de las casas de la fila superior con los tres círculos de la fila inferior si que ninguna de las líneas de conexión corte a otra.
Si representamos cada uno de los iconos (tanto las casas como los círculos) mediante puntos (vértices) y tomamos también las líneas de conexión (aristas) lo que obtenemos seria el siguiente grafo:
---------> K3,3

Llamando u1,u2,u3 a los vértices superiores y v1,v2,v3 a los inferiores y representando como ui, vj a la arista que une el vértice ui con el vértice vj obtenemos el grafo conocido como: K3,3


Partiendo de que dos aristas de un grafo sólo pueden contarse en un vértice (es decir, que si tenemos dibujados los vértices de antemano dos aristas no pueden cortarse en ningún punto nada más que en ellos).

Para intentar resolver este problema se usa el Teorema de Kuratowski:

Un grafo es plano si no contiene como subgrafo a K5(el grafo completo de 5 vértices) ni a K3,3.
Es decir, ni K5 ni K3,3 son grafos planos (ya que cada uno de ellos se contiene a sí mismo como subgrafo). O lo que es lo mismo, no pueden dibujarse en un papel con la condición de que ninguna arista corte a otra en un punto que no sea desde el principio un vértice.
En conclusión este juego por mas que intentemos encontrar una solución no se podra ya que no es un grafo plano (K3,3) .

Teorema (Formula de Euler):
"Si a y n son enteros primos relativos, entonces aφ(n) ≡ 1 (mod n)".
Sea M un mapa conexo con R regiones que represente al grafo G=(V, E), entonces:
V-E+R=2, es decir, R+V=E+2.
Sea G=(V, E) un grafo plano conexo, con V>2, entonces E3<=V-6
K5


Una subdivisión elemental de un grafo G es otro grafo, donde se sustituye una arista por
un nuevo vértice unido a los extremos de la arista suprimida por dos nuevas aristas.
En un mapa se trata de añadir un vértice sobre el interior de una arista existente.
Una subdivisión de un grafo G es el grafo obtenido efectuando un número finito (puede
ser 0) de subdivisiones elementales sucesivas.

Para K3,3
Si G es un grafo plano, conexo, con n vértices, q aristas y que
descompone al plano en r regiones (o caras), entonces

Demostración:
Por inducción sobre q
Si q=0, entonces n =1, r =1 y se cumple que n−q+r = 2
Supongamos que el resultado es cierto para todos los grafos planos
y conexos con q-1 aristas, donde q≥1.
Sea G un grafo plano y conexo con q aristas.

Si G no es árbol, entonces existe alguna arista a de un ciclo de G
G−{a} es plano, conexo con n vértices, q−1 aristas y r −1 regiones.
La hipótesis de inducción asegura entonces que:
n − (q−1)+ (r−1)= 2 , es decir, n−q+r = 2

Consecuencias
Si G es un grafo simple y planar con n vértices y q aristas
2.- Si n≥3 y G no tiene ciclos de longitud 3, entonces
q ≤ 2n−4
Ahora el borde de cada región tiene, al menos, 4 aristas y cada
arista pertenece al borde de dos regiones.
Así contando el nº de aristas, resulta que 4r ≤ 2q
Sustituyendo en la fórmula de Euler 2n−2q+2r = 4,
q ≤ 2n−4
3.- G tiene, al menos, un vértice v con grado d(v) ≤ 5
Si para cada vértice x, se tiene que d(x)≥6 entonces
2q=Σd(x) ≥ 6n, luego q≥3n

Aplicaciones:
El saber si un grafo es o no es plano puede ser de gran importancia en el diseño de circuitos integrados, de carreteras, de ferrocarriles y en general en todos los casos en que el cruce de dos aristas represente una situación incómoda (o incluso cara).


Conclusiones:
Este tema me gustó mucho en lo personal, ya que pude identificar como detectar si un grafo es plano o no. A base del juego y algunos grafos pude entender mejor este principio.
Sinceramente no fue fácil encontrar la información ya que es muy extenso este tema pero con dedicación y leyendo varias fuentes pude comprender la idea principal del tema.
Creo que me falto investigar mas ya que hay algunos aspectos cuales no logré comprender muy bien. Sobre la presentación quise poner la idea principal para que fuera concreta e invitarlos a que entraran a mi blog para que se familiarizaran mas con el problema.

8 comentarios:

  1. Oye en la primera imagen que esta en el blog(donde esta el cubo); segun yo (si es que no me equivoco)
    tanto el cubo como la figura que esta al lado son planos porque solo estamos viendo al cubo desde cierta perspectiva y si lo vemos desde otra perspectiva viene siendo la segunda figura. Osea son planos los dos porque son la misma figura pero vista desde otra perspectiva; si es que no me equivoco...

    ResponderEliminar
  2. Asi es, en parte tienes razon cinthia pero si en algun caso te dieran el grafo (en forma de cubo)desde esa perspectiva seria un grafo no plano, ya que algunas aristas se intersecan y para eso se analiza de distinta perspectiva para que el mismo grafo sea plano. Una forma de determinar si es el mismo grafo es contando las aristas (12)
    o en dado caso los vertices(8) es como un ejemplo que la profesora nos habia mencionado.
    Espero te ayude el comentario. Cualquier cosa me avisas. Gracias

    ResponderEliminar
  3. lo que mas me gusto fue el juego que pusiste en el salon , cuando mi compañero paso

    y la impresion de que no se podia resolver .

    buen trabajo.

    Pero tambien me quedaron dudas sobre lo que me comentan mis compañeros ariba , si puedieras explicarnos estaria super bien

    aqui dejo mi blog para que la profe nos pueda identificar http://doranellygonzalez.blogspot.com/

    ResponderEliminar
  4. hola gerardo muy buena tu exposicion como dice dora estuvo muy bien lo del ejemplo me gustaba que hicieran eso al igual que rocio que nos dio a colorear dos grafos porque hacen que pongamos mas atencion y participemos

    bueno en respuesta a lo que me preguntaste en mi blog bueno como ya sabemos un arbol es vertices conectados exactamente por un camino en el ejemplo de fibonacci un ejemplo que nos quedo muy claro cuando la maestra tania no lo explico que nos dio la frase de " divide y venceras" y nos explico que dividieramos como raiz seria fib(5)i saldria como hijos se podria decia lo que lo conforma fib(3)+ fib(4) asi sucesivamente ir reduciendo paso a paso para poder realizarlo no se si me explico. bueno en la vida lo podemos emplear en tantas cosas, problemas que se nos presenten que sean largos y se nos dificulten podemos dividirlo en partes e ir resolviendo paso a paso y asi llegar a realizar todo el problema en si. :D no se si me explico si no me entendiste algo o tienes otra duda no dudes en preguntarme

    dejo mi el link de mi blog
    http://klaudialozanoo.blogspot.com/

    ResponderEliminar
  5. Muy buena explicada de clase!
    ya me entretuve un ratillo con el juego de la casa y no lo puedo hacer ):
    puedes poner un ejemplo sencillo de el uso de planaridad en el diseño de de carreteras?, es que yo tengo una idea pero creo que estoy equivocado jaja
    su pudieras poner solo como se optimizaria te lo agradeceria :D

    ResponderEliminar
  6. Tavo: Supongamos que la carretera es el grafo de la estrella (K5) como te daras cuenta muchas de sus aristas se intersecan y esto quiere decir que en una carretera o un vehiculo va a transitar por el mismo camino (arista) supongamos que al recorrer el mismo camino estamos perdiendo tiempo y costos de traslado y no seria lo mas optimo por seguir. Es por eso que podemos analizar un grafo plano para trazar una ruta de camino en cuanto a la carretera y asi seguir un camino mas optimo para que no recorra el mismo camino. Espero haberte respondido bien, si aun tienes dudas me dices y analizamos juntos esa aplicacion

    ResponderEliminar
  7. Cynthia tiene toda la razón en su primer comentario. El grafo que es el cubo SIEMPRE es plano - planaridad implica que existe por lo menos una manera de dibujar el grafo así que no cruzcan las aristas, pero no exige de ninguna manera que TODOS los dibujos sean así.

    Por otro lado, el problema de planaridad en su forma básica es un problema de DECISIÓN donde la respuesta es sí (si es plano) o no (si no es plano). Una versión como problema de optimización sería preguntar por el número mínimo de cruces en cualquier dibujo que tenga (si es cero, es plano).

    ResponderEliminar
  8. grasias por responder a mis preguinta y con lo que la profe. puso ariba comprendi mejor el conecpto.

    que bueno que haigas entendido el analisis del problema que en al clase produjo confusion.

    peor si tienes dudas namas me avisas

    ResponderEliminar