Teorema de Hall#
Introducción#
Una pregunta teórica que lleva a muchas aplicaciones es la siguiente: ¿cuándo hay un emparejamiento en una gráfica bipartita? Para entender un poco el tipo de aplicaciones, consideremos la siguiente gráfica:
De manera abstracta, aquí sólo tenemos vértices y aristas. Sin embargo, podría ser que esta gráfica venga de un contexto particular. Por ejemplo, del lado izquierdo podemos tener los miembros de un equipo de trabajo en ciencia de datos. Del lado derecho podemos tener una lista de actividades que pueden realizar. Y puede que una arista de una persona a una tarea signifique que «sabe hacerla muy bien».
Así, Abi sabe trabajar muy bien con bases de datos, construir variables y escribir código, Bob sabe trabajar muy bien con bases de datos, construir variables y hacer estadística, etc.
Al encontrar un emparejamiento, podemos asignar a cada uno de ellos una tarea que sepan hacer muy bien de modo que no le toque más de una tarea a cada quien y de modo que ninguna tarea esté hecha por más de una persona.
Este emparejamiento es bastante bueno pues quedan 4 personas trabajando en 4 tareas. De hecho es un emparejamiento maximal. Sin embargo, sería ideal encontrar un emparejamiento con \(5\) aristas. Este sería un emparejamiento perfecto y haría que todas las tareas y todas las personas quedaran cubiertas.
Así como esta aplicación hay muchas más. El lado izquierdo pueden ser personas, el derecho potenciales empresas a donde pueden aplicar y una arista la intención de aplicar ahí. El lado izquierdo pueden ser perros por adoptar, el derecho personas y una arista que hay compatibilidad de adopción.
Teorema de Hall#
Con esto en mente, ¿cuándo podemos encontrar buenos emparejamientos en gráficas bipartitas? El resultado clave es el teorema de Hall.
Como preámbulo, tenemos el siguiente resultado, que nos da una condición necesaria «obvia» para que pueda existir un emparejamiento que cubra a todos los vértices de un lado de una gráfica bipartita.
Proposición. Si una gráfica bipartita con partición de vértices en \(A\) y \(B\) tiene un emparejamiento que cubre a \(A\), entonces para cualquier \(X\subseteq A\) se tiene que
Recuerda que \(N(X)\) es el conjunto de vértices que son vecinos de por lo menos un vértice en \(X\). La demostración de esta proposición queda de tarea moral.
Resulta que esta condición necesaria «obvia» también es una condición suficiente. Este es un resultado demostrado por Philip Hall, en 1935. A continuación presentamos una versión moderna.
Teorema (de Hall). Sea \(G\) una gráfica bipartita con partición de vértices en \(A\) y \(B\). Si para cualquier \(X\subseteq A\) se tiene que
Hay varias formas de demostrar este resultado. A continuación damos una que combina ideas de contradicción y principio extremo.
Demostración. Para buscar una contradicción, supongamos que bajo las hipótesis dadas la gráfica \(G\) no tiene un emparejamiento que cubra a \(A\). Tomemos un emparejamiento \(M\) de \(G\) que cubra a la mayor cantidad de vértices posibles de \(A\). Hay por lo menos un vértice \(v\) de \(A\) que \(M\) no cubre.
Diremos que una trayectoria es alternante si comienza en \(v\) y de manera alternante usa aristas fuera y dentro de \(M\).
Definimos los siguientes dos conjuntos:
Notemos que \(v\in X\). Probaremos las siguientes dos afirmaciones:
El emparejamiento \(M\) da una biyección \(\varphi: X\setminus\{v\} \to Y\) dada por \(\varphi(x)\) es el vértice de \(Y\) conectado con \(x\) en \(M\).
Se tiene que \(N(X)\subseteq Y\).
Para la primer afirmación:
La función \(\varphi\) está bien definida pues para llegar a un vértice de \(X\setminus \{v\}\) tiene que ser en una arista de la trayectoria «de \(B\) a \(A\)» que corresponde a las aristas de \(M\). Así, cada vértice en \(X\setminus \{v\}\) está conectado mediante \(M\) con un elemento de \(Y\).
La función \(\varphi\) es inyectiva pues \(M\) es emparejamiento.
La función \(\varphi\) es suprayectiva pues de no serlo, tendríamos una trayectoria alternante a un vértice \(y\) en \(Y\) que no se puede continuar (no hay arista de \(M\) en \(y\)). Pero en este caso el emparejamiento \(M\) podría agrandarse quitando las aristas de esta trayectoria en \(M\) y poniendo las que no estén en \(M\). Esto sería una contradicción a la maximalidad de \(M\).
Para la segunda afirmación, tomemos un vecino \(y\) de un vértice \(x\) en \(X\). Si \(x=v\), claramente \(y\) está en \(Y\) pues \(vy\) es una trayectoria alternante (de una arista). Si \(x\neq v\), tenemos dos casos. Si la arista \(xy\) no está en \(M\), entonces podemos tomar una trayectoria alternante hasta \(x\) y alargarla con la arista \(xy\) para llegar a \(y\), obteniendo \(y\in Y\). Si la arista \(xy\) está en \(M\), entonces la trayectoria alternante que llega a \(x\) pasa por \(y\) y entonces \(y\in Y\).
Usemos ambas afirmaciones para encontrar nuestra contradicción final. Tenemos la siguiente cadena de igualdades/desigualdades:
La primer desigualdad es por la segunda afirmación. La primer igualdad es por la biyección de la primer afirmación. La segunda desigualdad es por que \(X\) tiene a \(v\) y el otro conjunto no. Así, tenemos \(|N(X)|<|X|\) y esto contradice las hipótesis del teorema.
De esta manera, debe existir un emparejamiento que cubre a \(A\).
\(\square\)
Ya teniendo el teorema de Hall, es sencillo dar una caracterización de aquellas gráficas bipartitas que tienen un emparejamiento perfecto.
Corolario. Sea \(G\) una gráfica bipartita. Se tiene que \(G\) tiene un emparejamiento perfecto si y sólo si para cualquier subconjunto de vértices \(X\) de \(G\) se tiene que
Tarea moral#
Los siguientes problemas te ayudarán a practicar lo visto en esta entrada. Para resolverlos, necesitarás usar herramientas matemáticas, computacionales o ambas.
Encuentra un emparejamiento perfecto en la gráfica de la introducción.
Muestra la proposición «obvia» de la sección «Teorema de Hall», es decir, que si \(G\) tiene un emparejamiento que cubre a \(A\), entonces para cualquier \(X\subseteq A\) se tiene que \(|X|\leq |N(X)|\).
Demuestra el corolario de la sección «Teorema de Hall» que caracteriza a las gráficas bipartitas que tienen un emparejamiento perfecto.
Sea \(G\) una gráfica bipartita en donde los grados de todos los vértices son iguales a un mismo entero \(r\geq 1\).
Demuestra que ambos lados de la partición en vértices tendrán la misma cantidad de vértices.
Demuestra que la gráfica tiene un emparejamiento perfecto.
La baraja inglesa de \(52\) cartas consiste de cuatro palos (corazones, diamantes, picas y tréboles) y trece cartas por palo (\(A,2,\ldots,9,10,J,Q,K\)). Se revuelve la baraja completamente. Ya que las cartas están revueltas, se hacen 13 montones de cartas, cada uno con \(4\) cartas. Demuestra que es posible elegir una carta del primer montón, una del segundo, una del tercero, etc. de modo que las \(13\) cartas elegidas precisamente sean un \(A\), un \(2\), un \(3\), etc. hasta un \(K\).