# TDA | Practica 6 ejercicio 1 ## Consigna - TBD # ## Resolución ### a) - Si la capacidad de cada arista de $N$ es par $\Rightarrow F_{max} \equiv 0$ (mod 2) - **Propiedad de flujo máximo**: Cualquier flujo a través de una red debe cumplir con la capacidad de las aristas y la suma del flujo que entra a cualquier nodo no fuente, debe ser igual a la suma del flujo que sale de ese vértice. - Ahora supongamos que **Existe una arista con capacidad $2k \ \forall k \in \mathbb{Z}$**. El flujo máximo a través de esa arista tiene que ser $2k$ o menos, pero tiene que ser par por propiedad de los números enteros (no pienso indagar en teoría de números). - Para cada vértice excepto $s$ y $t$, el flujo que entra y el que sale tiene que ser equilibrado, es decir que si el flujo entrante es la suma de números pares, entonces la suma también es par. ### b) - Si la capacidad de cada arista de $N$ es par $\Rightarrow$ existe un flujo máximo en el cual el flujo sobre cada arista de $N$ es par. - par + par = par. - La explicación es la misma que para el inciso a ### c) - Si la capacidad de cada arista de $N$ es **impar**, entonces el valor del flujo máximo es impar. - $s \to u_1:$ coste 3, $u_1 \to t$: coste 1 - $s \to u_2$: coste 3, $u_2 \to t$: coste 1 - $\therefore F_{max}=2$. -  ### d) - Si la capacidad de cada arista de $N$ es impar $\Rightarrow$ existe un flujo máximo en el cual el flujo sobre cara arista de $N$ es impar. - Más falso que el amor que siente por mí: -  ### e) - TBD