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
