Emparejamiento

Teoría

En teoría de gráficas, un emparejamiento $M$ en una gráfica $G = (V, E)$ es un conjunto de aristas que no comparten vértices. Dicho de otra forma, no hay dos aristas en $M$ que compartan un extremo. Un emparejamiento es perfecto si cubre todos los vértices de la gráfica. Aunque puedes estudiar los emparejamientos en gráficas generales, aparecen más seguido en la combinatoria de olimpiada dentro del contexto de gráficas bipartitas. Esto suele aparecer como el "Problema del Matrimonio", donde buscas emparejar elementos de un conjunto $A$ (por ejemplo, aplicantes) con elementos distintos de un conjunto $B$ (por ejemplo, trabajos) de tal forma que cada pareja sea válida.

El estudio de los emparejamientos es fundamental para los problemas de existencia en combinatoria. Te da las herramientas rigurosas para determinar cuándo es posible una configuración o asignación específica. La intuición central gira en torno a los "cuellos de botella". Si un subconjunto de $k$ vértices en una parte de una gráfica bipartita está conectado colectivamente a menos de $k$ vecinos, es imposible tener un emparejamiento que cubra ese subconjunto. Esta observación lleva al Teorema del Matrimonio de Hall, que asegura que la ausencia de tal cuello de botella no solo es necesaria, sino suficiente para que exista un emparejamiento.