De mis clases: el problema del matrimonio

El martes pasado, en la Facultad de Ciencias, tuvimos la visita del Bachillerato #26 de la Universidad de Colima, del municipio de Ixtlahuacán. Los casi 40 estudiantes fueron divididos en dos grupos: mientras uno de ellos visitaba el Laboratorio de Microscopía Electrónica de la facultad, el otro estaría a cargo de alguno de los profesores. Yo me hice cargo de uno de los grupos y decidí invitarlos a mi clase de Matemáticas Discretas II. El tema correspondiente era el del problema del matrimonio.

El problema consiste en lo siguiente: supongamos que queremos formar parejas entre hombres y mujeres de un grupo de personas. Cada hombre conoce a cierto número de mujeres y cada mujer conoce a cierto número de hombres, y suponemos que la acción de conocer a alguien es mutua. ¿Podemos formar dichas parejas de tal forma que todos se apareen con un conocido?

GrafoBipartito En términos de la teoría de grafos, podemos representar el problema por medio de un grafo G, donde cada persona es un vértice y la acción de conocer a alguien es una arista. No nos importa si las mujeres o los hombres se conocen entre sí, solo entre ellos, por lo que entonces los vértices del grafo G están partidos en dos conjuntos A y B de tal forma que las aristas solo unen vértices entre ambos, como se ve en la figura de la derecha. A un grafo así se le llama un grafo bipartito. Un apareamiento perfecto en G es una selección de aristas en el grafo bipartito G (o sea, un subgrafo) tal que cada vértice de A está unido a un solo vértice de B. Apareamiento Por ejemplo, del grafo de la derecha podemos construir el apareamiento perfecto descrito por las aristas rojas de la figura de la izquierda.

Podemos enunciar entonces el problema del matrimonio de la siguiente forma: dado un grafo bipartito G, ¿podemos encontrar un apereamiento perfecto en G?

Está claro que la respuesta es no en general, y que ciertas hipótesis deben cumplirse en el grafo G. Por ejemplo, el número de vértices en A debe ser el mismo que en B. Así que nos preguntamos, ¿cuáles son las hipótesis necesarias y suficientes para que un grafo bipartito G tenga un apareamiento perfecto?

Podemos ver que una hipótesis necesaria es que, dado cierto número de vértices en A, entonces dichos vértices deben tener, entre todos, al menos el mismo número de vértices vecinos (o sea, conectados por una arista) en B para poder ser apareados. Claramente la hipótesis inversa es también necesaria: cualquier número de vértices en B deben tener al menos el mismo número de vecinos en A. Sin embargo, ambas hipótesis son equivalentes si A y B tienen el mismo número de vértices en total.

Las hipótesis descritas en los párrafos anteriores son necesarias pero, ¿son equivalentes? La respuesta es sí, y es el contenido del llamado teorema del matrimonio, mostrado por Philip Hall en 1935.

Teorema del matrimonio. Sea G un grafo bipartito en igual número de vértices A y B. Entonces G tiene un apareamiento perfecto si y solo si cada número de vértices en A tiene al menos el mismo número de vértices vecinos en B.

En la clase demostramos este teorema. La demostración no es muy técnica, aunque sí extensa como para este blog, y pareció agradarles a los estudiantes de preparatoria.


Para más entradas de mis clases: de mis clases.

Esta entrada participa en la edición 4.12 del Carnaval de Matemáticas, cuyo blog anfitrión es High Ability Dimension.

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s