Teorema de corte mínimo de flujo máximo

En informática y teoría de la optimización , el teorema de flujo máximo y corte mínimo establece que en una red de flujo , la cantidad máxima de flujo que pasa de la fuente al sumidero es igual al peso total de los bordes en un corte mínimo , es decir, el menor peso total de los bordes que, si se quitaran, desconectaría la fuente del fregadero.

Este es un caso especial del teorema de dualidad de programas lineales y se puede utilizar para derivar el teorema de Menger y el teorema de König-Egerváry . ^[1]

El teorema relaciona dos cantidades: el caudal máximo a través de una red, y la capacidad mínima de un corte de la red, es decir, la capacidad mínima la alcanza el caudal.

Sea $N = (V, E)$ una gráfica dirigida , donde V denota el conjunto de vértices y E es el conjunto de aristas. Sean $s \in V$ y $t \in V$ la fuente y el sumidero de $N$ , respectivamente.

La capacidad de un borde es un mapeo denotada por $c$ $uv$ o $c$ $($ $u$ $,$ $v$ $)$ , donde $u$ $,$ $v$ $\in$ $V$ . Representa la cantidad máxima de flujo que puede pasar a través de un borde. ${\ Displaystyle c: E \ to \ mathbb {R} ^ {+}}$

Un flujo es un mapeo denotado por o , sujeto a las dos restricciones siguientes: ${\ Displaystyle f: E \ to \ mathbb {R} ^ {+}}$ ${\ Displaystyle f_ {uv}}$ ${\ Displaystyle f (u, v)}$

Una red con el valor de caudal igual a la capacidad de un corte st.

Una formulación en red del problema de selección de proyectos con la solución óptima.

Cada nodo negro denota un píxel.