Redes De Flujoss

Red de flujo
De Wikipedia, la enciclopedia libre
Saltar a: navegación, búsqueda
En teoría de grafos, una red de flujo es un grafo dirigido donde existen dos vértices especiales, uno llamado fuente,al que se le asocia un flujo positivo y otro llamado sumidero que tiene un flujo negativo y a cada arista se le asocia cierta capacidad positiva. En cada vértice diferente a los dos especiales semantiene la ley de corrientes de Kirchoff, en donde la suma de flujos entrantes a un vértice debe ser igual a la suma de flujos que salen de él. Puede ser utilizada para modelar el tráfico en un sistemade autopistas, fluidos viajando en tuberías, corrientes eléctricas en circuitos eléctricos o sistemas similares por lo que viaje algo entre nodos.
teorema de flujo máximo
Tenemos el conocido problemade flujo máximo o maximal: ¿cuál es la tasa mayor a la cual el material puede ser transportado de la fuente al sumidero sin violar ninguna restricción de capacidad?
En otras palabras, el problemaconsiste en determinar la máxima capacidad de flujo que puede ingresar a través de la fuente y salir por el nodo de destino.
El procedimiento para obtener el flujo máximo de una red, consiste enseleccionar repetidas veces cualquier trayectoria de la fuente al destino y asignar el flujo máximo posible en esa trayectoria.
Capacidad residual: es la capacidad adicional de flujo que un arco puede llevar:* Dada una red de flujo máximo, plantee la red residual asociada.
* Encuentre la trayectoria de la fuente al destino con capacidad de flujo estrictamente positivo (si no existe alguno, es porque se ha encontrado el óptimo).
* Examine estas trayectorias para encontrar la rama o arco con la menor capacidad de flujo restante e incremente en éste valor, la capacidad del flujo en sentidocontrario.
* Determine todas las trayectorias estrictamente positivas, hasta que no se permita flujo del nodo a un nodo destino.

Algoritmo de Ford-Fulkerson
De Wikipedia, la enciclopedia libre...