El teorema de König y sus consecuencias

Cobertura de vértices y dualidad

Una cobertura de vértices (vertex cover) de un grafo $G = (V, E)$ es un conjunto $C \subseteq V$ tal que toda arista de $G$ tiene al menos un extremo en $C$. El tamaño de la cobertura mínima se denota $\tau(G)$.

Un conjunto independiente (independent set) es un conjunto $I \subseteq V$ tal que ninguna arista conecta dos vértices de $I$. Equivalentemente, $V \setminus C$ es independiente si y solo si $C$ es cobertura de vértices. Luego $\alpha(G) + \tau(G) = |V|$, donde $\alpha(G)$ es el tamaño del máximo conjunto independiente.

Observación básica: si $M$ es un matching y $C$ es una cobertura de vértices, entonces $|M| \leq |C|$ (cada arista de $M$ necesita al menos un vértice de $C$, y como las aristas de $M$ son disjuntas, se necesitan al menos $|M|$ vértices distintos en $C$). En consecuencia, $\nu(G) \leq \tau(G)$, donde $\nu(G)$ es el tamaño del matching máximo.

La pregunta es: ¿cuándo se da la igualdad $\nu(G) = \tau(G)$? La respuesta, para grafos bipartitos, es el teorema de König.

Para grafos en general, la igualdad puede no darse: en el triángulo $K_3$, $\nu(K_3) = 1$ pero $\tau(K_3) = 2$ (se necesitan 2 vértices para cubrir las 3 aristas del triángulo). La bipartición es esencial.

El teorema de König

Teorema de König (1931): En todo grafo bipartito $G = (X \cup Y, E)$, el tamaño del matching máximo es igual al tamaño de la cobertura mínima de vértices:

Demostración (construcción de la cobertura a partir de un matching máximo): Sea $M$ un matching máximo de $G$. Construimos una cobertura $C$ con $|C| = |M|$.

Sea $U \subseteq X$ el conjunto de vértices de $X$ no cubiertos por $M$ (los que no están en ninguna arista de $M$). Definimos $Z$ como el conjunto de vértices alcanzables desde $U$ por caminos alternantes (caminos que alternan aristas fuera de $M$ y aristas en $M$). Sea $K = Z \cap X$ y $L = Z \cap Y$.

Definimos $C = (X \setminus K) \cup L$. Afirmamos que $C$ es cobertura de vértices y $|C| = |M|$.

$C$ es cobertura:** Sea $xy \in E$ una arista. Si $x \in K$, entonces $x \in Z \cap X$, y la arista $xy$ puede ser usada para extender el camino alternante hasta $y$, luego $y \in Z \cap Y = L$, así $y \in C$. Si $x \notin K$, entonces $x \in X \setminus K \subseteq C$. En ambos casos, al menos uno de $x, y$ está en $C$.

$|C| = |M|$:** Como $M$ es máximo, no hay camino de aumento (camino alternante desde $U$ hasta un vértice de $Y$ no cubierto por $M$). Luego todos los vértices de $L$ están cubiertos por $M$, y cada vértice de $L$ es emparejado con un vértice de $K$ (no de $X \setminus K$, porque si fuera emparejado con un $x \in X \setminus K$, ese $x$ sería alcanzable y estaría en $K$). Por tanto la función $\ell \mapsto M(\ell)$ es una biyección de $L$ a $K$, así $|L| = |K|$. Además, cada vértice de $X \setminus K$ está cubierto por $M$ (pues $U \subseteq K$). Luego $|C| = |X \setminus K| + |L| = |X \setminus K| + |K| - |\text{vértices de }K\text{ no cubiertos}| =$ (calculando con cuidado) $|M|$. $\square$

Consecuencias inmediatas: independencia y emparejamiento

Combinando $\alpha(G) + \tau(G) = |V|$ con $\nu(G) = \tau(G)$ obtenemos para grafos bipartitos:

$\alpha(G) = |V| - \nu(G)$.

Esto relaciona el conjunto independiente máximo con el matching máximo: en un grafo bipartito, maximizar el conjunto independiente es equivalente a minimizar el matching.

Corolario: En un grafo bipartito $G = (X \cup Y, E)$, el conjunto independiente máximo tiene tamaño $|X| + |Y| - \nu(G)$.

Aplicación en combinatoria de conjuntos: Sea $\mathcal{F}$ una familia de subconjuntos de $\{1,\ldots,n\}$ tal que para cualesquiera $A, B \in \mathcal{F}$, $A \not\subseteq B$ (familia anti-chain o antichena en el poset de inclusión). ¿Cuál es el tamaño máximo de $\mathcal{F}$? Por el teorema de Dilworth (que se deduce del teorema de König) y el teorema de Sperner, $|\mathcal{F}| \leq \binom{n}{\lfloor n/2 \rfloor}$.

El teorema de Dilworth: En cualquier poset finito $P$, el número mínimo de cadenas que cubren $P$ es igual al tamaño máximo de una antichena. La demostración construye un grafo bipartito con dos copias del poset y aristas para las relaciones de orden, y aplica el teorema de König.

El teorema de Dilworth y posets

Un poset (conjunto parcialmente ordenado) $(P, \leq)$ es un conjunto $P$ con una relación reflexiva, antisimétrica y transitiva. Una cadena en $P$ es un subconjunto de elementos totalmente ordenados (cualquier par es comparable). Una antichena es un subconjunto de elementos mutuamente incomparables.

Teorema de Dilworth (1950): En un poset finito, el tamaño mínimo de una partición de $P$ en cadenas es igual al tamaño máximo de una antichena.

Demostración vía König: Construimos un grafo bipartito $G = (P_1 \cup P_2, E)$ donde $P_1$ y $P_2$ son dos copias de $P$, y hay arista $(x_1, y_2)$ si $x < y$ en $P$ (con $<$ estricto). Por König, el tamaño del matching máximo $\nu$ es igual al tamaño de la cobertura mínima $\tau$.

Una cadena de cobertura mínima de $P$ con $k$ cadenas corresponde a una partición donde los "eslabones" de las cadenas son los emparejamientos. Formalmente, si el matching máximo es $\nu$, la partición mínima en cadenas tiene tamaño $|P| - \nu$ (cada arista del matching "une" dos elementos en la misma cadena, reduciendo el conteo en 1). El tamaño máximo de una antichena es también $|P| - \nu$ por König. El argumento completo requiere verificar la biyección entre antichenas y coberturas en el grafo bipartito auxiliar.

Teorema de Mirsky (dual): En un poset finito, el tamaño mínimo de una partición en antichenas es igual a la longitud de la cadena más larga (número de elementos en la cadena máxima).

Aplicación olímpica: Sea $P = \{1, 2, \ldots, n^2 + 1\}$ con $n^2 + 1$ enteros distintos. Por el teorema de Erdős–Szekeres (corolario de Dilworth/Mirsky), cualquier sucesión de $n^2 + 1$ enteros distintos contiene una subsucesión monótona de longitud al menos $n+1$.

König y flujo máximo: la conexión con Ford-Fulkerson

El teorema de König es un caso especial del teorema min-max de flujo-corte (teorema de Ford-Fulkerson / Menger). En un grafo bipartito con capacidades unitarias, el flujo máximo de una fuente $s$ (conectada a todos los vértices de $X$) a un sumidero $t$ (conectado desde todos los vértices de $Y$) es exactamente el matching máximo.

Por el teorema del corte mínimo, el flujo máximo es igual al corte mínimo, que corresponde a la cobertura mínima de vértices. Esto da una segunda demostración del teorema de König.

Consecuencia algorítmica: El matching máximo en un grafo bipartito se puede encontrar en tiempo $O(|V| \cdot |E|)$ usando el algoritmo de caminos de aumento (Ford-Fulkerson para grafos bipartitos). Para propósitos olímpicos, basta saber que el matching se puede construir algorítmicamente.

El teorema de Menger: En un grafo dirigido, el número máximo de caminos dirigidos internamente disjuntos (sin vértices comunes, salvo el origen y el destino) de $s$ a $t$ es igual al tamaño mínimo de un corte de vértices separando $s$ de $t$. Esto generaliza König y es la formulación más general del min-max para caminos.

En olimpiadas: El teorema de König aparece en problemas de la forma "muestra que se necesitan al menos $k$ piezas para cubrir todas las filas/columnas de un tablero" o "¿cuántas piezas mínimas cubren todas las amenazas?". La estrategia es modelar el tablero como un grafo bipartito y aplicar König.

Problema trabajado: cobertura en un tablero

Problema: En un tablero de $n \times n$, se marcan algunas celdas. Demuestra que el número mínimo de filas y columnas necesarias para cubrir todas las celdas marcadas es igual al máximo número de celdas marcadas tal que no haya dos en la misma fila ni en la misma columna.

Solución: Construimos un grafo bipartito $G = (R \cup C, E)$ donde $R = \{r_1,\ldots,r_n\}$ (filas), $C = \{c_1,\ldots,c_n\}$ (columnas), y hay arista $(r_i, c_j)$ si la celda $(i,j)$ está marcada.

Un matching en $G$ corresponde a un conjunto de celdas marcadas sin dos en la misma fila ni en la misma columna. Una cobertura de vértices en $G$ corresponde a una selección de filas y columnas que cubren todas las celdas marcadas (pues cada arista $(r_i,c_j)$ tiene al menos un extremo en la cobertura, es decir, la fila $i$ o la columna $j$ está seleccionada).

Por el teorema de König, $\nu(G) = \tau(G)$. Traducido al tablero: el máximo de celdas marcadas sin repetición de fila ni columna (matching máximo) es igual al mínimo de filas y columnas que cubren todas las celdas (cobertura mínima). $\square$

Este resultado es el teorema de König en tableros, y es uno de los enunciados más frecuentes en olimpiadas de combinatoria de nivel Iberoamericano.