miércoles, 19 de mayo de 2010

proyecto


Para el proyecto 5 escogí el tema de Flujo Máximo por algoritmo Push->relabel el tema trata de lo siguiente:

El problema de Flujo Máximo: consiste en encontrar un flujo factible a través de un solo proveedor, en una sola red de flujo que es máxima.

Dada una red de flujo G ( V ,E ) con capacidad de un nodo u al nodo v dado como c ( u ,v ) , fuente s y un fregadero t , queremos encontrar la máxima cantidad de flujo puedes enviar desde sa t a través de la red . Hay dos tipos de operaciones se llevan a cabo en los nodos, empuje yreetiquetado.


Empuje: -->Un impulso de u a v significa enviar una parte del exceso de flujo en u a v.Tres condiciones deben cumplirse para que un empuje a tener lugar:
  • Más flujo en el nodo que fuera de él hasta ahora
  • La capacidad disponible de la U de V.
  • Sólo se puede enviar a menor nodo
-->Reetiqueta: Si no todos los vecinos se han intentado desde el pasado reetiquetar:

Tratamos de empujar el flujo a un vecino no probado.


Un ejemplo:



el flujo máximo es: 5


Porque?

tienes un inicio s con dos salidas ambas con capacidad de 3, bien analizas la primera en este caso io elegí 'p', con capacidad 3, después seguí a 'r' con una capacidad de 2 y de 'r' llegue a 't' que es mi punto final, aquí es donde etiqueto según las capacidades de r->t (3/3), de p->r (2/2) y de s->p (2/3), ahora analizo la siguiente salida posible de s->o con capacidad 3, después 'o' tiene dos posibles salidas una con capacidad de 2 hacia 'p' pero si volvemos a analizar 'p' vemos que ya no tiene capacidad para otro flujo, entonces nos regresamos a 'o' y analizamos la salida a 'q' que tiene capacidad 3, después 'q' tiene otras dos posibles salidas hacia 'r' y hacia 't' y pues en este caso si vamos hacia 'r' nos topamos de nuevo con que ya no tiene capacidad para otro flujo entonces nos vamos por la salida hacia 't' y etiquetamos... q->t (2/2), o->q (2/3) y de s->o (2/3) ahora... sumamos los flujos resultantes q->t (2/2) y r->t (3/3) y el total es 5.. entonces el flujo máximo es 5.. :)


auto evaluación:
En lo personal este tema me agrado mucho, aunque siendo sincera escogí este tema porque me llamo la atención el nombre, y mi sorpresa fue que al buscar info no encontraba.. D: pero después de mucho leer en Internet, encontré algunas cosas y aunque al principio no entendía bien, ahora ya lo entiendo...
Bien espero y sea de su agrado y cualquier cosa pregunten.. =D

9 comentarios:

  1. quisiera saber cual es la complejidad del algorimo ??

    ResponderEliminar
  2. El tiempo de ejecución para este algoritmo es de O(V2E).
    O también como mencione en la clase si lo complementas con un árbol dinámico de Sleator y Tarjan se ejecuta en O ( V E log( V 2/ E )) tiempo. Y en ocaciones en mas eficiente que otros algoritmos de flujo como el de Edmonds-Karp.

    ResponderEliminar
  3. Hola cuando mencionaste en clase lo de empuje y retiqueta en el grafo mas la explicacion de la profesora pude comprender la idea principal del problema. Pero solo tenga una pequeña duda.
    Como se puede aplicar esto en una situacion en la vida cotidiana?
    Saludos!

    ResponderEliminar
  4. Pues bien podría ser en una red de agua potable.. por ejemplo de una ciudad a otra.. por ejemplo.. aquí en monterrey si lo ubicas en un mapa y observas desde donde se transporta el agua y los puntos hacia donde se dirige puedes encontrar el flujo máximo de agua que habría en la cuidad.
    Me explique..? jeje.. =)

    ResponderEliminar
  5. Si, me imagine el mapa de la ciudad y lo que seria el transporte del flujo de agua hacia varios puntos. Me quedo claro, gracias!

    ResponderEliminar
  6. hola adriana yo tambien tenia la duda de un ejemplo en la vida aunque fue la misma duda de gerardo no entendi muy bien como hacerlo

    ResponderEliminar
  7. a miraa ya subi una imagen.. se me habia pasado.. peroo deja te lo explico a detalle en la publicacion.. =D

    ResponderEliminar
  8. yo tambien iba a preguntar su aplicacion
    gracias por la respuesta del ejemplo en la vida cotidiana, ya entendi mejor :D
    Muy buena clase!
    Saludos!

    ResponderEliminar
  9. El problema de flujo máximo es un modelo matemático para la mayoría de aplicaciones de transporte. Puede ser una tubería también, claro, pero igual modela a tránsito vehicular, selección de rutas y cargas de trailers, etc.

    ResponderEliminar