LISTAS RELACIONADAS CON LAS MATEMÁTICAS - ALGORITMOS

método de Ford-Fulkerson o algoritmo de Ford-Fulkerson ( FFA ) es un algoritmo codicioso que calcula el flujo máximo en una red de flujo . A veces se le llama "método" en lugar de "algoritmo", ya que el enfoque para encontrar rutas de aumento en un gráfico residual no se especifica completamente ^[1] o se especifica en varias implementaciones con diferentes tiempos de ejecución. ^[2] Fue publicado en 1956 por LR Ford, Jr. y DR Fulkerson . ^[3] El nombre "Ford – Fulkerson" también se usa a menudo para el algoritmo de Edmonds-Karp, que es una implementación completamente definida del método Ford-Fulkerson.

La idea detrás del algoritmo es la siguiente: siempre que haya una ruta desde la fuente (nodo de inicio) al sumidero (nodo final), con capacidad disponible en todos los bordes de la ruta, enviamos flujo a lo largo de una de las rutas. Luego encontramos otro camino, y así sucesivamente. Una ruta con capacidad disponible se llama ruta de aumento .

Algoritmo [ editar ]

Dejar $${\ displaystyle G (V, E)}ser un gráfico, y para cada borde de u a v , vamos$${\ displaystyle c (u, v)} ser la capacidad y $${\ displaystyle f (u, v)}ser el flujo Queremos encontrar el flujo máximo de la fuente s al sumidero t . Después de cada paso en el algoritmo se mantiene lo siguiente:

Limitaciones de capacidad	$${\ displaystyle \ forall (u, v) \ en E: \ f (u, v) \ leq c (u, v)}	El flujo a lo largo de un borde no puede exceder su capacidad.
Simetría sesgada	$${\ displaystyle \ forall (u, v) \ en E: \ f (u, v) = - f (v, u)}	El flujo neto de u a v debe ser opuesto al flujo neto de v a u (ver ejemplo).
Conservación de flujo	$${\ displaystyle \ forall u \ in V: u \ neq s {\ text {y}} u \ neq t \ Rightarrow \ sum _ {w \ in V} f (u, w) = 0}	El flujo neto a un nodo es cero, excepto por la fuente, que "produce" flujo, y el sumidero, que "consume" flujo.
Valor (f)	$${\ displaystyle \ sum _ {(s, u) \ en E} f (s, u) = \ sum _ {(v, t) \ en E} f (v, t)}	El flujo que sale de s debe ser igual al flujo que llega a t .

Esto significa que el flujo a través de la red es un flujo legal después de cada ronda en el algoritmo. Definimos la red residual. $${\ displaystyle G_ {f} (V, E_ {f})} Ser la red con capacidad. $${\ displaystyle c_ {f} (u, v) = c (u, v) -f (u, v)}y no hay flujo. Observe que puede suceder que se permita un flujo de v a u en la red residual, aunque no está permitido en la red original: si{\ displaystyle f (u, v)> 0} y $${\ displaystyle c (v, u) = 0} entonces {\ displaystyle c_ {f} (v, u) = c (v, u) -f (v, u) = f (u, v)> 0}.

Algoritmo Ford – Fulkerson

Entradas dadas una red$${\ displaystyle G = (V, E)}con capacidad de flujo c , un nodo fuente s y un nodo sumidero t

Salida Calcular un flujo f de s a t de valor máximo

1. $${\ displaystyle f (u, v) \ leftarrow 0} para todos los bordes $${\ displaystyle (u, v)}
2. Mientras que hay un camino p de s a t en$${\ displaystyle G_ {f}}, tal que {\ displaystyle c_ {f} (u, v)> 0} para todos los bordes $${\ displaystyle (u, v) \ in p}:
   1. Encontrar $${\ displaystyle c_ {f} (p) = \ min \ {c_ {f} (u, v) :( u, v) \ in p \}}
   2. Para cada borde $${\ displaystyle (u, v) \ in p}
      1. $${\ displaystyle f (u, v) \ leftarrow f (u, v) + c_ {f} (p)}( Enviar flujo a lo largo del camino )
      2. $${\ displaystyle f (v, u) \ leftarrow f (v, u) -c_ {f} (p)}( El flujo puede ser "devuelto" más tarde )

• "←" denota la asignación . Por ejemplo, " artículo ← más grande " significa que el valor de los cambios más grandes en el valor del artículo .
• " return " termina el algoritmo y genera el siguiente valor.

La ruta en el paso 2 se puede encontrar, por ejemplo, con una búsqueda en primer lugar (BFS) o una búsquedaen profundidad en$${\ displaystyle G_ {f} (V, E_ {f})}. Si usa el primero, el algoritmo se llama Edmonds – Karp .

Cuando no se puedan encontrar más rutas en el paso 2, s no podrá alcanzar t en la red residual. Si S es el conjunto de nodos alcanzables por s en la red residual, entonces la capacidad total en la red original de bordes desde S hasta el resto de V es, por una parte, igual al flujo total que encontramos desde s hasta t , y por otro lado, sirve como un límite superior para todos estos flujos. Esto prueba que el flujo que encontramos es máximo. Véase también el teorema de corte mínimo de flujo máximo .

Si la grafica $${\ displaystyle G (V, E)} tiene múltiples fuentes y sumideros, actuamos de la siguiente manera: Supongamos que $${\ displaystyle T = \ {t | t {\ text {es un sumidero}} \}} y $${\ displaystyle S = \ {s | s {\ text {es una fuente}} \}}. Añadir una nueva fuente$${\ displaystyle s ^ {*}} con un borde $${\ displaystyle (s ^ {*}, s)} desde $${\ displaystyle s ^ {*}} a cada nodo $${\ displaystyle s \ en S}con capacidad $${\ displaystyle c (s ^ {*}, s) = d_ {s} \; (d_ {s} = \ sum _ {(s, u) \ en E} c (s, u))}. Y añada un nuevo fregadero.$${\ displaystyle t ^ {*}} con un borde $${\ displaystyle (t, t ^ {*})} de cada nodo $${\ displaystyle t \ in T} a $${\ displaystyle t ^ {*}}con capacidad $${\ displaystyle c (t, t ^ {*}) = d_ {t} \; (d_ {t} = \ sum _ {(v, t) \ en E} c (v, t))}. Luego aplique el algoritmo Ford-Fulkerson.

Además, si un nodo u tiene restricción de capacidad$${\ displaystyle d_ {u}}, reemplazamos este nodo con dos nodos $${\ displaystyle u_ {in}, u_ {out}}, y una ventaja $${\ displaystyle (u_ {in}, u_ {out})}con capacidad $${\ displaystyle c (u_ {in}, u_ {out}) = d_ {u}}. Luego aplique el algoritmo Ford-Fulkerson.

Complejidad [ editar ]

Al agregar la ruta de aumento de flujo al flujo ya establecido en el gráfico, se alcanzará el flujo máximo cuando ya no se puedan encontrar más rutas de aumento de flujo en el gráfico. Sin embargo, no hay certeza de que esta situación sea alcanzada, por lo que lo mejor que se puede garantizar es que la respuesta será correcta si el algoritmo termina. En el caso de que el algoritmo se ejecute para siempre, el flujo podría incluso no converger hacia el flujo máximo. Sin embargo, esta situación solo ocurre con valores de flujo irracional. Cuando las capacidades son enteros, el tiempo de ejecución de Ford – Fulkerson está limitado por$${\ displaystyle O (Ef)}(ver gran notación O ), donde$${\ displaystyle E} es el número de aristas en el gráfico y $${\ displaystyle f}Es el flujo máximo en el gráfico. Esto se debe a que cada ruta de aumento se puede encontrar en$${\ displaystyle O (E)} tiempo y aumenta el flujo en una cantidad entera de al menos $${\ displaystyle 1}, con el límite superior $${\ displaystyle f}.

Una variación del algoritmo Ford-Fulkerson con terminación garantizada y un tiempo de ejecución independiente del valor de flujo máximo es el algoritmo Edmonds-Karp , que se ejecuta en$${\ displaystyle O (VE ^ {2})} hora.

Ejemplo integral [ editar ]

El siguiente ejemplo muestra los primeros pasos de Ford – Fulkerson en una red de flujo con 4 nodos, fuente $${\ displaystyle A} y hundirse $${\ displaystyle D}. Este ejemplo muestra el peor comportamiento del algoritmo. En cada paso, solo un flujo de$${\ displaystyle 1}Se envía a través de la red. Si en su lugar se utilizara la primera búsqueda de amplitud, solo se necesitarían dos pasos.

Camino	Capacidad	Red de flujo resultante
Red de flujo inicial
$${\ displaystyle A, B, C, D}	{\ displaystyle {\ begin {alineado} & \ min (c_ {f} (A, B), c_ {f} (B, C), c_ {f} (C, D)) \\ = & \ min ( c (A, B) -f (A, B), c (B, C) -f (B, C), c (C, D) -f (C, D)) \\ = & \ min (1000) -0,1-0,1000-0) = 1 \ end {alineado}}}
$${\ displaystyle A, C, B, D}	{\ displaystyle {\ begin {alineado} & \ min (c_ {f} (A, C), c_ {f} (C, B), c_ {f} (B, D)) \\ = & \ min ( c (A, C) -f (A, C), c (C, B) -f (C, B), c (B, D) -f (B, D)) \\ = & \ min (1000) -0,0 - (- 1), 1000-0) = 1 \ final {alineado}}}
Después de 1998 más pasos ...
Red de flujo final

Observe cómo el flujo es "rechazado" desde $${\ displaystyle C} a $${\ displaystyle B} al encontrar el camino $${\ displaystyle A, C, B, D}.

Ejemplo sin terminación [ editar ]

Considere la red de flujo que se muestra a la derecha, con la fuente $${\ displaystyle s}, lavabo $${\ displaystyle t}, capacidades de bordes $${\ displaystyle e_ {1}}, $${\ displaystyle e_ {2}} y $${\ displaystyle e_ {3}} respectivamente $${\ displaystyle 1}, $${\ displaystyle r = ({\ sqrt {5}} - 1) / 2} y $${\ displaystyle 1} y la capacidad de todos los demás bordes algún número entero $${\ displaystyle M \ geq 2}. El constante$${\ displaystyle r} fue elegido para que $${\ displaystyle r ^ {2} = 1-r}. Usamos rutas de aumento de acuerdo con la siguiente tabla, donde$${\ displaystyle p_ {1} = \ {s, v_ {4}, v_ {3}, v_ {2}, v_ {1}, t \}}, $${\ displaystyle p_ {2} = \ {s, v_ {2}, v_ {3}, v_ {4}, t \}} y $${\ displaystyle p_ {3} = \ {s, v_ {1}, v_ {2}, v_ {3}, t \}}.

Paso	Camino de aumento	Flujo enviado	Capacidades residuales
			$${\ displaystyle e_ {1}}	$${\ displaystyle e_ {2}}	$${\ displaystyle e_ {3}}
0			$${\ displaystyle r ^ {0} = 1}	$${\ displaystyle r}	$${\ displaystyle 1}
1	$${\ displaystyle \ {s, v_ {2}, v_ {3}, t \}}	$${\ displaystyle 1}	$${\ displaystyle r ^ {0}}	$${\ displaystyle r ^ {1}}	$${\ displaystyle 0}
2	$${\ displaystyle p_ {1}}	$${\ displaystyle r ^ {1}}	$${\ displaystyle r ^ {2}}	$${\ displaystyle 0}	$${\ displaystyle r ^ {1}}
3	$${\ displaystyle p_ {2}}	$${\ displaystyle r ^ {1}}	$${\ displaystyle r ^ {2}}	$${\ displaystyle r ^ {1}}	$${\ displaystyle 0}
4	$${\ displaystyle p_ {1}}	$${\ displaystyle r ^ {2}}	$${\ displaystyle 0}	$${\ displaystyle r ^ {3}}	$${\ displaystyle r ^ {2}}
5	$${\ displaystyle p_ {3}}	$${\ displaystyle r ^ {2}}	$${\ displaystyle r ^ {2}}	$${\ displaystyle r ^ {3}}	$${\ displaystyle 0}

Tenga en cuenta que después del paso 1, así como después del paso 5, las capacidades residuales de los bordes $${\ displaystyle e_ {1}}, $${\ displaystyle e_ {2}} y $${\ displaystyle e_ {3}} están en la forma $${\ displaystyle r ^ {n}}, $${\ displaystyle r ^ {n + 1}} y $${\ displaystyle 0}, respectivamente, para algunos $${\ displaystyle n \ in \ mathbb {N}}. Esto significa que podemos utilizar rutas de aumento.$${\ displaystyle p_ {1}}, $${\ displaystyle p_ {2}}, $${\ displaystyle p_ {1}} y $${\ displaystyle p_ {3}}Infinidad de veces y las capacidades residuales de estos bordes siempre estarán en la misma forma. El flujo total en la red después del paso 5 es$${\ displaystyle 1 + 2 (r ^ {1} + r ^ {2})}. Si continuamos utilizando rutas de aumento como las anteriores, el flujo total converge a$${\ displaystyle \ textstyle 1 + 2 \ sum _ {i = 1} ^ {\ infty} r ^ {i} = 3 + 2r}, mientras que el flujo máximo es $${\ displaystyle 2M + 1}. En este caso, el algoritmo nunca termina y el flujo ni siquiera converge al flujo máximo. ^[4]

Implementación de Python del algoritmo de Edmonds-Karp [ editar ]

 colecciones de importación
 
# Esta clase representa un gráfico dirigido utilizando la 
clase de  representación de matriz de adyacencia Gráfico :
  
    def  __init__ ( self , graph ): 
        self . graph  =  graph   # residual graph 
        self . ROW  =  len ( gráfico )
  
    def  BFS ( self ,  s ,  t ,  parent ): 
        '' 'Devuelve true si hay una ruta desde la fuente' s 'hasta el hundimiento' t 'en el 
        gráfico residual. También llena el padre [] para almacenar la ruta '' '

        # Marcar todos los vértices como no visitados 
        visitados  =  [ Falso ]  *  ( self . ROW )
         
        # Crear una cola para la 
        cola  BFS =  colecciones . deque ()
         
        # Marque el nodo de origen como visitado y póngalo en 
        cola . apéndice ( s ) 
        visitado [ s ]  =  Verdadero
         
        # Bucle BFS estándar 
        mientras que la  cola : 
            u  =  cola . gente ()
         
            # Obtener todos los vértices adyacentes del vértice eliminado de la cola u 
            # Si no se ha visitado un adyacente, 
            márquelo # visitado y póngalo en la cola 
            para  ind ,  val  en  enumerate ( self . Graph [ u ]): 
                if  ( visitó [ ind ]  ==  Falso )  y  ( val  >  0 ): 
                    cola . añadir ( ind ) 
                    visitó [ ind ]  =  verdadero 
                    padre [ ind ] =  u
 
        # Si llegamos a hundirnos en BFS a partir de la fuente, devolvemos 
        # verdadero, de lo contrario, se 
        devuelve una  visita falsa [ t ]
             
    # Devuelve el flujo máximo de s a t en la 
    definición del  gráfico dado EdmondsKarp ( self ,  source ,  sink ):
 
        # Esta matriz se llena con BFS y para almacenar la ruta 
        principal  =  [ - 1 ]  *  ( self . ROW )
 
        max_flow  =  0  # No hay flujo inicialmente
 
        # Aumentar el flujo mientras que hay camino desde la fuente al sumidero 
        , mientras que  uno mismo . BFS ( fuente ,  sumidero ,  padre ):
 
            # Encuentre la capacidad residual mínima de los bordes a lo largo de la 
            ruta # rellenada por BFS. O podemos decir encontrar el flujo máximo 
            # a través de la ruta encontrada. 
            path_flow  =  float ( "Inf" ) 
            s  =  sink 
            mientras  s  ! =  source : 
                path_flow  =  min ( path_flow ,  self . graph [ parent [ s ]] [ s ]) 
                s  =  parent [ s ]
 
            # Agregar flujo de ruta al flujo general 
            max_flow  + =  ruta_flujo
 
            # actualizar las capacidades residuales de los bordes y revertir los bordes 
            # a lo largo de la ruta 
            v  =  hundir 
            mientras que  v  ! =   fuente : 
                u  =  padre [ v ] 
                self . gráfico [ u ] [ v ]  - =  path_flow 
                self . gráfico [ v ] [ u ]  + =  ruta_flujo 
                v  =  padre [ v ]
 
        devolver  max_flow