Gestalte GoConqr mit. Was sollen wir als Nächstes hinzufügen?

Mindmap

Flujo Maximo

Sergio Roa Spanisch

Inhalt der Mindmap

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).

Informationen

Beschreibung
Mindmap am Flujo Maximo, erstellt von Sergio Roa am 22/10/2017.
Erstellt von
Sergio Roa
Aufrufe
0
Bewertung

Mehr zu Flujo máximo en redes

Feedback

Worum geht es?

Was sollen wir als Nächstes hinzufügen?