Ayúdanos a dar forma a GoConqr. ¿Qué deberíamos añadir?

Mapa mental

Flujo Maximo

Sergio Roa Español

Contenido del mapa

Flujo Maximo

  1. 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.
  2. 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
  3. 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.
  4. 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.
  5. 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).

Información

Descripción
Mapa Mental sobre Flujo Maximo, creado por Sergio Roa el 22/10/2017.
Creado por
Sergio Roa
Visitas
0
Valoración

Más sobre Flujo máximo en redes

Escríbenos

¿Sobre qué es tu mensaje?

¿Qué deberíamos añadir?