Skip to Content
CTRL K

One Billion Shades of Grey

Editorial oficial 

Asumo que ya

Esta explicación busca aclarar cómo se deriva el grafo de flujo de costo mínimo.

Esencialmente, queremos hallar la mejor cota inferior posible de la respuesta, que resulta ser igual a la respuesta por dualidad.

Como menciona el editorial, queremos minimizar ∑cu,v\sum c_{u,v} sujeto a algunas desigualdades de la forma

Eq(u,v)=[cu,v≥xu−xv]. \text{Eq}(u,v)=\left[c_{u,v}\ge x_u-x_v\right].

Cada cu,v≥0c_{u,v}\ge 0, y algunos xux_u están fijos (para las baldosas del borde) mientras que los demás no están acotados (si ignoramos la restricción de que cada xi∈[1,109]x_i\in [1,10^9]). Esencialmente, queremos una combinación lineal de estas ecuaciones

Eq=∑au,vEq(u,v) \text{Eq}=\sum a_{u,v}\text{Eq}(u,v)

tal que se cumplan las siguientes condiciones.

  • Cada au,va_{u,v} corresponde al flujo en una arista del grafo de flujo de costo mínimo, así que deben ser no negativos.
  • En el lado izquierdo de Eq\text{Eq}, ningún cu,vc_{u,v} tiene coeficiente mayor que uno. Esto corresponde a au,v+av,u≤1a_{u,v}+a_{v,u}\le 1, es decir que el flujo en cada arista del grafo de flujo de costo mínimo es a lo sumo 11.
  • Los coeficientes de cada xux_u no constante en el lado derecho de Eq\text{Eq} son cero. Esto significa que en el grafo de flujo de costo mínimo, cada vértice (salvo la fuente y el sumidero) tiene el mismo flujo de entrada que de salida.
  • La constante del lado derecho se maximiza (queremos la mejor cota inferior posible).

Ejemplo: (debería aclarar lo de arriba)

Supongamos que

c4,5≥x4−x5 c_{4,5}\ge x_4-x_5 c2,5≥x2−x5 c_{2,5}\ge x_2-x_5 c5,1≥x5−x1 c_{5,1}\ge x_5-x_1 c5,3≥x5−x3 c_{5,3}\ge x_5-x_3

y que xi=ix_i=i para cada 1≤i≤41\le i\le 4 mientras que x5x_5 no está acotado. ¿Cuál es el menor valor posible de

∑cu,v=c4,5+c2,5+c5,1+c5,3? \sum c_{u,v}=c_{4,5}+c_{2,5}+c_{5,1}+c_{5,3}?

Solución: En este caso, la respuesta es 4−1=34-1=3. Podemos mostrar que esto es una cota inferior eligiendo

a4,5=1,a2,5=0,a5,1=1,a5,3=0. a_{4,5}=1, a_{2,5}=0, a_{5,1}=1, a_{5,3}=0.

Entonces obtenemos la combinación lineal

Eq=a4,5⋅[c4,5≥x4−x5]+a5,1⋅[c5,1≥x5−x1] \text{Eq}=a_{4,5}\cdot \left[c_{4,5}\ge x_4-x_5\right]+a_{5,1}\cdot \left[c_{5,1}\ge x_5-x_1\right] 1⋅[c4,5≥x4−x5]+1⋅[c5,1≥x5−x1] 1\cdot \left[c_{4,5}\ge x_4-x_5\right]+1\cdot \left[c_{5,1}\ge x_5-x_1\right] Eq=[c4,5+c5,1≥x4−x1]. \text{Eq}=[c_{4,5}+c_{5,1}\ge x_4-x_1].

Se sigue que

∑cu,v≥c4,5+c5,1≥x4−x1=4−1=3. \sum c_{u,v}\ge c_{4,5}+c_{5,1}\ge x_4-x_1=4-1=3.

Esto corresponde a un grafo de flujo de costo mínimo con 55 vértices más una fuente y un sumidero donde todas las aristas tienen capacidad 11.

  • Dibujar aristas de 44 a 55, de 22 a 55, de 55 a 11 y de 55 a 33 con costo 00.
  • Dibujar aristas de la fuente al vértice 44 con costo 44 y de la fuente al vértice 22 con costo 22.
  • Dibujar aristas del vértice 33 al sumidero con costo −3-3 y del vértice 11 al sumidero con costo −1-1.
  • Hallar el flujo de costo máximo de la fuente al sumidero. En este caso, enviamos una unidad de flujo por
source→4→5→1→sink. \text{source}\to 4\to 5\to 1\to \text{sink}.

En el problema original las aristas van en ambos sentidos (no solo en uno), pero la idea es similar.

Fundamentos