14.1: Introducción

Antes de ahondar en los problemas combinatorios particulares que deseamos considerar en este capítulo, expondremos un teorema clave. Al trabajar con problemas de flujo de red, nuestros ejemplos hasta ahora siempre han tenido capacidades enteras y siempre encontramos un flujo máximo en el que cada borde llevaba una cantidad entera de flujo. No es, sin embargo, inmediatamente obvio que esto siempre se pueda hacer. ¿Por qué, por ejemplo, no podría darse el caso de que el flujo máximo en una red particularmente patológica con capacidades enteras sea 23/3? ¿O qué tal algo aún peor, como\(\sqrt{21 \pi}\)? Podemos descartar esto último porque los problemas de flujo de red caen en una clase mayor de problemas conocidos como problemas de programación lineal, y un teorema mayor nos dice que si un programa lineal se plantea con todas las restricciones enteras (capacidades en nuestro caso), la solución debe ser un número racional. No obstante, en el caso de los flujos de red, algo aún más fuerte es cierto.

Teorema 14.1

En un problema de flujo de red en el que cada borde tiene capacidad entera, hay un flujo máximo en el que cada borde lleva una cantidad entera de flujo.

Observe que el teorema anterior no garantiza que cada flujo máximo tenga flujo entero en cada borde, solo que seamos capaces de encontrar uno. Con este teorema en la mano, ahora vemos que si consideramos problemas de flujo de red en los que las capacidades son todas 1 podemos encontrar un flujo máximo en el que cada borde lleve un flujo de 0 o 1. Esto nos puede dar una interpretación combinatoria del flujo, en cierto sentido utilizando los bordes completos como bordes que “tomamos” en algún sentido útil.