Mapa mental
Flujo Maximo
Conteúdo do mapa
Flujo Maximo
Existe un flujo que viaja desde un único lugar de origen hacia un único lugar de destino a través de arcos que conectan nodos intermediarios.
- Los arcos tienen una capacidad máxima de flujo
- Se trata de enviar desde la fuente al destino la mayor cantidad posible de flujo.
Definiciones básicas
- Flujo
- Circulación de unidades homogéneas de un lugar a otro.
- Capacidad de flujo
- capacidad de unidades que pueden entrar por el nodo fuente y salir por el nodo destino.
- Origen o fuente de flujo
- nodo por el cual el flujo ingresa
- Destino o Sumidero de flujo
- nodo por el cual el flujo sale
- Capacidades residuales
- capacidades restantes unas vez que el flujo pasa el arco
- Flujo
resolución de problemas de flujo máximo se requiere el uso del método
- Ford Fulkerson
- Este método propone buscar caminos en los que se pueda aumentar el flujo hasta que se alcance el flujo máximo
- El flujo es siempre positivo y con unidades enteras.
- El flujo a través de un arco es menor o igual que la capacidad
- El flujo que entra en un nodo es igual al que sale de él.
- Este método propone buscar caminos en los que se pueda aumentar el flujo hasta que se alcance el flujo máximo
- Ford Fulkerson
Resolución de problema
- 1. Se identifica el nodo origen y destino.
- 2. Se parte desde el nodo de origen y se escoge el arco que posea mayor flujo
- 3. Se identifica los nodos de transbordo.
- 4. Repetir como si el nodo intermediario fuera el nodo origen.
- 5. Se calcula "k" y las capacidades nuevas.
- 6. Dado el resultado se cambian las capacidades y se repite el mismo procedimiento desde el inicio.
Formulario
- Cij,ji =(Ci-K, Cj+K), donde:
- C: capacidad
- Ij: índices de los nodos
- K: es el minimo flujo que pasa por el nodo, se calcula como k= min(capacidades de la ruta).
- Cij,ji =(Ci-K, Cj+K), donde:
Informações
- Descrição
- Mapa Mental sobre Flujo Maximo, criado por Sergio Roa em 22-10-2017.
- Criado por
- Sergio Roa
- Visualizações
- 0
- Avaliação
Mais sobre Flujo máximo en redes