# Flujo ###### tags: `temas 2do Parcial` ## Resumen ### Glosario/definiciones * $F_\max = c(S_\min) = ∑_{e \in SS^c} c(e)$ * En cada iteración de FF, la cantidad de flujo que aumentamos ($f_c(e)$) está determinada por la arista de menor capacidad del camino de aumento $P$ que encontramos: * $f_c(e) = \min(c(e) \text{ tal que } e ∈ P)$ * $c$: Capacidad/peso de la arista * $P$: Camino de aumento * Corte: Conjunto de vértices ### Trucos * Para encontrar maxima cant de caminos disjuntos en aristas, se puede usar flujo con capacidad = 1 para toda arista * Si tenemos libertad para elegir la capacidad de una arista en un problema que estamos modelando con flujo, tratar de usar números bajos y todos iguales para tener mejor complejidad (por ejemplo 1 y 0, no infinito aunque funcione) * Convertir grafo en digrafo convirtiendo cada arista en 2 arcos: uno de ida y uno de vuelta * La complejidad de EK $O(m²n)$ da mejor en grafos con pocas aristas (porque tiene m²), en cambio la de FF $O(Fm)$ da mejor en grafos dispersos/ralos/sparse. ### Errores comunes * En los ejercicios de modelado de flujo: * Olvidarse de aclarar cuál vértice es la fuente y cuál el sumidero (por más de que se llamen s y t). * Olvidarse de aclarar qué representa cada unidad de flujo y qué representa la capacidad * Olvidarse de transformar al grafo en digrafo (cada arista se convierte en 2 arcos: ida y vuelta) ## Ejercicios de la guia 5 ### Propiedades de los flujos en redes ### 1: Demostrar o dar contraejemplo #### a) Si la capacidad de cada arista de N es par, entonces el valor del flujo máximo es par. Verdadero $F_{\max} = c(S_{\min}) = ∑_{e \in SS^c} c(e) =_{\text{por hipótesis}} ∑_{e \in SS^c} 2 g(e) = 2 ∑_{e \in SS} g(e) \text{ es par }_\square$ $\text{Definimos } g(e) = c(e)/2$ #### b) Si la capacidad de cada arista de N es par, entonces existe un flujo máximo en el cual el flujo sobre cada arista de N es par. Reformulo: Para toda red con aristas de capacidad par, existe un flujo máx en el cual el flujo sobre cada arista es par. En cada iteración del algoritmo de FF, se encuentra un camino de aumento. La cantidad de flujo que podremos enviar por él estará limitada por la capacidad de la arista de menor capacidad del camino. Por ende, en cada iteración encontramos un camino por el que enviaremos una cantidad par (la capacidad de la arista de menor capacidad del camino) de flujo. Pero al tener todas las aristas capacidad par, sabemos que siempre estaremos aumentando el flujo en una cantidad par. Y como la suma de pares es par y FF encuentra el $F_\max$, sabemos que el flujo que estaremos enviando por cada arista cuando sigamos este algoritmo será par. Ejemplo: ```graphviz digraph{ s -> a [label=" (capacidad: 2, flujo: 2) "] a -> b [label=" (2, 2) "] a -> c [label=" (2, 0) "] b -> t [label=" (2, 2) "] c -> t [label=" (2, 0) "] } ``` En este ejemplo, si bien cada arista tiene capacidad par, hay aristas en las cuales el flujo es impar. #### c) Si la capacidad de cada arista de N es impar, entonces el valor del flujo máximo es impar. Falso: ```graphviz digraph{ s -> a [label=" (capacidad: 3, flujo: 2) "] a -> b [label=" (1, 1) "] a -> c [label=" (1, 1) "] b -> t [label=" (1, 1) "] c -> t [label=" (1, 1) "] } ``` #### d) Si la capacidad de cada arista de N es impar, entonces existe un flujo máximo en el cual el flujo sobre cada arista de N es impar. Reformulo: Para toda red con arcos de capacidad impar, existe un flujo máximo en el cual el valor del flujo sobre todas las aristas es impar. Contraejemplo sería: una red con arcos de capacidad impar en la que no existe **ningún flujo máximo** en el cual el valor del flujo sobre **todas** las aristas sea impar. Falso: ```graphviz digraph{ s -> a [label=" (capacidad: 1, flujo: 1) "] s -> b [label=" (1, 1) "] a -> c [label=" (1, 1) "] b -> c [label=" (1, 1) "] c -> t [label=" (3, 2) "] } ``` Es contraejemplo porque: i) Cumple que todas las aristas tienen capacidad impar, pero ii) en el único flujo máximo posible, el valor del flujo del arco que llega a $t$ es 2 y por lo tanto par. #### e) Si todas las aristas de N tienen capacidades racionales, entonces el flujo máximo es racional. El valor del $F_\max = c(S_\min)$. Entonces, como todas las capacidades son racionales y los racionales son cerrados para la suma, $c(S_\min) = \sum_{e \in SS^c} c(e) = F_\max$ es racional. ### 2: Para todo $F ∈ \mathbb{N}$, construir una red con 4 vértices y 5 aristas en la que el método de Ford y Fulkerson necesite $F$ iteraciones en peor caso para obtener el flujo de valor máximo (partiendo de un flujo inicial con valor 0). ```graphviz {engine="circo"} digraph{ s -> a [label=" capacidad: F/2 "] s -> b [label=" F/2 "] a -> b [label=" 1 "] a -> t [label=" F/2 "] b -> t [label=" F/2 "] } ``` En el peor caso FF siempre elige un camino de aumento en el que pasa por la arista de capacidad 1, entonces siempre aumenta el flujo en esa cantidad, necesitando $F$ iteraciones para obtener el flujo de valor máximo (si partimos desde el flujo de valor 0). ### 3. Determinar la complejidad del algoritmo de Edmonds y Karp para encontrar el flujo máximo de una red N cuando: #### a) No hay información acerca de las capacidades de las aristas de N. $O(m²n)$ Buscamos los caminos de aumento con BFS ($O(mn)$) y cada arista aparece $O(n)$ veces en un camino de aumento. * Cada arco puede ser crítico max n/2 veces. * Hay 2m arcos potencialmente críticos. $=>$ nm iteraciones * Cada camino de aumento puede ser encontrado en $O(m)$ porque examina cada arco a lo sumo una vez. $∴$ EK sin información sobre las capacidades de las aristas $∈ O(nm²)$. #### b) Todas las aristas de N tienen capacidad a lo sumo $q << n$. $O(nmq)$ #### c) El flujo máximo de N tiene un valor $F << mn$. Acotamos mn por F, para tener una cota más justita: $O(Fm)$ ### 4: Proponer un algoritmo lineal que dada una red N y un flujo de valor máximo, encuentre un corte de capacidad mínima de N 1) Obtener la red residual: Para cada arista comparamos el flujo que pasa por ella con su capacidad: $O(m)$ 2) Obtener el corte mínimo S: BFS desde $s$: $O(n+m)$ 3) Obtener las aristas que cruzan el corte: Por cada arista verificamos su pertenece a S: $O(m)$ $∴$ la complejidad del algoritmo propuesto es $O(n+m)$. ### Problemas de modelado I: caminos disjuntos en un grafo ### 5. Sea G un digrafo con dos vértices s y t. #### a) Proponer un modelo de flujo para determinar la máxima cantidad de caminos disjuntos en aristas que van de s a t. * s: fuente * t: sumidero * unidades de flujo enteras indivisibles * capacidad 1 en todas las aristas ```graphviz digraph{ s -> a [label="1"] s -> b [label="1"] s -> c [label="1"] s -> d [label="1"] a -> b [label="1"] a -> t [label="1"] b -> t [label="1"] c -> t [label="1"] d -> c [label="1"] } ``` #### b) Dar una interpretación a cada unidad de flujo y cada restricción de capacidad. Unidad de flujo: Representa un camino. Capacidad: Es 1 porque cada arista la podemos contar como máximo una vez. #### c) Demostrar que el modelo es correcto * Práctica Flujo 1/2 2C20 0h45': https://youtu.be/HKqVI5DvlUI?t=2726 (No piden tanto en el final igual pareciera) #### d) Determinar la complejidad de resolver el modelo resultante con el algoritmo de Edmonds y Karp. $O(m²n)$ ### 6. Sea G un grafo con dos vértices s y t. #### a) Proponer un modelo de flujo determinar la máxima cantidad de caminos disjuntos en vértices que unen a s y t. ```graphviz digraph G{ s -> a [label=""] s -> b [label=""] s -> c [label=""] s -> d [label=""] a -> b [label=""] a -> t [label=""] b -> t [label=""] c -> t [label=""] d -> c [label=""] } ``` ```graphviz digraph Gp{ s -> a_in [label="1"] a_in -> a_out [label="1"] s -> b_in [label="1"] b_in -> b_out [label="1"] s -> c_in [label="1"] c_in -> c_out [label="1"] s -> d_in [label="1"] d_in -> d_out [label="1"] a_out -> b_in [label="1"] a_out -> t [label="1"] b_out -> t [label="1"] c_out -> t [label="1"] d_out -> c_in [label="1"] } ``` #### b) Dar una interpretación a cada unidad de flujo y cada restricción de capacidad. * Unidad de flujo: Representa un camino. * Capacidad: Es 1 en las aristas $v_{in} → v_{out}$ porque cada vértice lo podemos contar como máximo una vez. En las aristas preexistentes podríamos poner un valor arbitrario mayor a 0, pero usamos también 1 para acotar la complejidad de FF. #### c) Demostrar que el modelo es correcto. Idem #### d) Determinar la complejidad de resolver el modelo resultante con el algoritmo de Edmonds y Karp. $O(m²n)$ ### 7. Un grafo $G$ es k-conexo cuando $G∖W$ es conexo para todo $W ⊆ V (G)$ con $|W| = k − 1$. #### a) Proponer un modelo de corte mínimo para determinar el máximo k tal que $G$ es k-conexo. ```graphviz digraph Gp{ "s" -> a_in [label="1"] a_in -> a_out [label="1"] s -> b_in [label="1"] b_in -> b_out [label="1"] s -> c_in [label="1"] c_in -> c_out [label="1"] s -> d_in [label="1"] d_in -> d_out [label="1"] a_out -> b_in [label="1"] a_out -> t [label="1"] b_out -> t [label="1"] c_out -> t [label="1"] d_out -> c_in [label="1"] } ``` #### b) Dar una interpretación a cada unidad de flujo y cada restricción de capacidad. #### c) Demostrar que el modelo es correcto. #### d) Determinar la complejidad de resolver el modelo resultante con el algoritmo de Edmonds y Karp. ### Problemas de modelado II: asignación ### 8 #### a) ``` f1 m1 s f2 m2 t ⋮ ⋮ ff mn s -> fi tiene capacidad fi fi -> mj tiene capacidad cij mj -> t tiene capacidad mj ``` ```graphviz {engine="dot"} digraph{ s -> f1 [label=" f1"] s -> f2 [label=" f2 "] s -> ff [label=" ff "] f1 -> m1 f1 -> m2 f1 -> mn ff -> m1 ff -> m2 ff -> mn f2 -> m1 f2 -> m2 f2 -> mn [label=""] m1 -> t [label=" m1 "] m2 -> t [label=" m2 "] mn -> t [label=" mn "] } ``` #### b) * Unidad de flujo: una persona de una familia en una mesa * Restricción de capacidad: #### c) Armar el grafo es $O(|F| + |F||M| + |M|) = O(|F||M|)$. Correr EK (modificado para devolver los caminos de aumento) es $O(m²n) = O((|F||M|)²(|F|+|M|))$. Como EK es un caso particular de FF, también podemos expresar la complejidad como $O(Fm) = O((\sum_{i = 1}^n f_i) \ m)$ que será una cota más ajustada. ### 9: Sean $r_1, ..., r_m$ y $c_1, ..., c_n$ números naturales. Se quiere asignar los valores de las celdas de una matriz de $m × n$ con números naturales de forma tal que la i-ésima fila sume $r_i$ y la i-ésima columna sume $c_i$ #### a) Modelar el problema de asignación como un problema de flujo. #### b) Dar una interpretación a cada unidad de flujo y cada restricción de capacidad. #### c) Demostrar que el modelo es correcto. #### d) Determinar la complejidad de resolver el modelo resultante con el algoritmo de Edmonds y Karp. ### 10: Dado un ordenamiento $v_1, ..., v_n$ de los vértices de un digrafo $D$, se define la secuencia digráfica de D como $(d⁻(v_1), d⁺(v_1)), ..., (d⁻(v_n), d⁺(v_n))$. Dada una secuencia de pares $d$, el problema de realización de $d$ consiste en encontrar un digrafo $D$ cuya secuencia digráfica sea $d$. #### a) Modelar el problema de realización como un problema de flujo. ``` v1 w1 s v2 w2 t ⋮ ⋮ vn wn s -> vi con capacidad d⁺(vi) vi -> vj, i≠j con capacidad 1 vj -> t con capacidad d⁻(vj) ``` ```graphviz digraph{ s -> v1 s -> v2 s -> vn v1 -> w2 v1 -> wn v2 -> w1 v2 -> wn vn -> w1 vn -> w2 w1 -> t w2 -> t wn -> t } ``` * sin respuesta (aun?), pero mismo problema: https://math.stackexchange.com/questions/3577883/construct-graph-using-max-flow-algorithm #### b) Dar una interpretación a cada unidad de flujo y cada restricción de capacidad. La unidad de flujo que pasa por los ejes vi -> wj representa un arco entre vi y vj en el digrafo resultado. La unidad de flujo que pasa por ejes que involucran a la fuente s o al sumidero t representa las restricciones en cuanto a los grados de entrada y salida de los nodos del digrafo resultado. #### c) Demostrar que el modelo es correcto. <!-- ![](https://external-content.duckduckgo.com/iu/?u=https%3A%2F%2Fgifimage.net%2Fwp-content%2Fuploads%2F2017%2F10%2Fdying-of-laughter-gif-3.gif&f=1&nofb=1) --> #### d) Determinar la complejidad de resolver el modelo resultante con el algoritmo de Edmonds y Karp. La cota debe estar expresada en función de n y debe ser lo suficientemente ajustada. $O(|V|² + m²n)$ $m = |V|²$ $n = |V|$ $=> O(|V|² + m²n) = O(m²n) = O(|V|⁴|V|) = O(|V|⁵)$ Más ajustado: $m \in O(n²)$ $F \in O(n(n-1)) = O(n²)$ $=> O(mF) = O(n²n²) = O(n⁴)$ ### 11: Un grafo mixto es una tripla $G = (V, E, A)$ tal que $(V, E)$ es un grafo, $(V, A)$ es un grafo orientado y $E$ y $A$ no tienen aristas en común. (En otras plabras, $G$ se obtiene del grafo $(G, E ∪ A)$ orientando las aristas de $A$). El grafo mixto $G$ es euleriano si se pueden orientar las aristas de E a fin de que el grafo orientado resultante tenga un recorrido que pase por todas sus aristas. Es sabido que un digrafo es euleriano si y sólo si el digrafo es conexo y $d⁺(v) = d⁻(v)$ para todo $v ∈ V(G)$. a) Modelar el problema de decidir si un grafo mixto es euleriano como un problema de flujo. > Cada hint más quemadora que la anterior. Sugiero no mirar todas de una y spoilearte, sino ver si sale a cada una. > Hint: Imaginá que es agua lo que fluye, y está fluyendo por las aristas en el mismo orden que lo hace un ciclo euleriano. > Hint 2: Considerá el grafo residual. > Hint 3: c(e) = 1 en todas las aristas en el residual. > Hint 4: Quién son s y t en el flujo? > Hint 5: Cuánto tiempo toma el algoritmo de flujo que elegiste, en este grafo? > Hint 6 Algoritmo de Hierholzer > [name=Federico Lebron] [time=Mon, Jan 26, 2022 16:44 PM] * S6.4-5 Algoritmo de Hierholzer | | UPV: * https://www.youtube.com/watch?v=4q4l8ohNmD4 * https://www.youtube.com/watch?v=3QkVXYsrTVs b) Dar una interpretación a cada unidad de flujo y cada restricción de capacidad. c) Demostrar que el modelo es correcto. d) Determinar la complejidad de resolver el modelo resultante con el algoritmo de Edmonds y Karp.