Una fiesta con 28 invitados

—Tú serás el encargado de preparar las bolsas de caramelos, Ot —sentenció Sal.

—¡Mola! —respondió Ot.

—Eso no puede ser, Sal —protestó Germán —Porque entonces Ula no podrá ayudar en nada para la fiesta.

—No pasa nada — añadió Jose —Como es tan pequeña, puede jugar mientras los demás preparamos la fiesta.

—Yo me quedo jugando con ella para que no se aburra, ¿verdad Ula? —propuso Elio —¿Quieres que te enseñe a dibujar un unicornio?

—De eso nada —intervino Ven —Hay 7 tareas que hacer y 7 niños. Si uno no ayuda, una de las tareas se quedará sin hacer…; Además, ¡no puedes dejar a Ula sin tarea! ¡Llorará y llorará!

—No somos 7, somos 8, Ven —dijo el pequeño Gonzalo y añadió —¡Ya sé contar!

—¿Estás insinuando que yo haga algo? —protestó Ven —Es mi cumpleaños, ¡yo soy el jefe!

Ula contemplaba la escena sin mucha pasión, estaba arreglando los pliegues de su precioso tutú. Aquella mañana nuestros amigos Sal y Ven estaban muy bien acompañados, estaban Elio, Ot, Ula, Germán, Gonzalo y Jose. Por la tarde celebrarían la fiesta de cumpleaños de Ven y los habían invitado a pasar el día en casa para jugar y para ayudar a organizar las actividades del cumpleaños.

—¿Puedes ayudar a mamá con la tarta, Ula? —preguntó el gafotas dulcemente a la pequeña bailarina.

—No, de eso nada —interrumpió de nuevo Gonzalo —Eso me lo he pedido yo.

—Tú puedes hacer otra cosa Gonzalo —respondió Jose.

—Sí, claro —añadió Elio —Si quieres que Gonzalo escriba las pistas del tesoro… ¡si no sabe escribir!

—Pero bueno… —Mati acababa de entrar —cuánto niño guapo por esta casa…

—¡Mati! —gritaron todos los niños a la vez, Gauss respiró tranquilo. Siempre que la pelirroja llegaba se acababan estas acaloradas discusiones.

—Hola Mati —dijo Sal —Estamos intentando asignar las tareas para preparar la fiesta de cumpleaños de Ven. Pero tenemos un lío…

—Pero ¿cómo lo estáis organizando? —preguntó la gafotas.

—Mira —continuó hablando el gafotas —en esta tabla, he ido apuntando, como en el juego de los barquitos, qué tarea quería hacer cada uno. Hay 7 tareas: llenar los globos de agua, pintar los huevos de colores para la carrera con cuchara, rellenar bolsas con caramelos, ayudar a mamá con la tarta, poner galletas en los platos, escribir las pistas para el tesoro escondido y hacer las tarjetas binarias para la magia.

—Ajá, muy bien chicos —dijo Mati —¿Y qué es lo que pasa?

—Que o nos sobran tareas —contestó Ven —O nos faltan niños…

—¿Por qué no lo hacéis dibujando el grafo? —propuso Mati.

—¿Qué es un grafo ? —preguntó Gemán.

—Es un dibujito —respondió Ven —Con unos puntos, que se llaman vértices y unas líneas que unen a algunos de esos puntos, que se llaman aristas ¿Verdad, Mati?

—Eso es —confirmó Mati —Vamos a pintar un vértice por cada niño y otro por cada tarea. Y uniremos cada niño con las tareas que ha pedido hacer, ¿os parece?

—¡Mola! —gritaron a la vez Ot y Gonzalo.

—Qué bonito te ha quedado ese grafo Mati…

—Gracias, Jose —dijo Mati —Lo que vosotros queréis hacer es lo que se llama en Teoría de Grafos, un emparejamiento, es decir, elegir de ese grafo un conjunto de aristas que emparejen a cada niño con una tarea diferente. Es más, lo que queréis hacer se llama emparejamiento completo, porque no queréis que ningún niño se quede de brazos cruzados, ¿verdad?

—Verdad —contestó Gemán.

—Bueno, yo no voy a hacer nada —añadió Ven —Es mi fiesta de cumpleaños y ….

—Y no estás en el grafo, Ven —interrumpió Elio —No te va a tocar nada.

—¿Se podrá hacer Mati? —preguntó el gafotas —¿Se podrá hacer el emparejamiento completo?

—Vamos a verlo Sal —anunció la pelirroja —Y lo vamos a ver de la siguiente manera: me iréis diciendo una asignación de tareas como queráis, siempre asignando a cada niño una de las que él se ha pedido; si lo conseguimos de entrada, estupendo y nos ponemos a trabajar. Si no conseguimos el emparejamiento completo, os enseñaré un método que nos permitirá asignar una pareja más si es posible, así hasta llegar al emparejamiento completo; si en algún momento no es posible añadir una pareja más y no tenemos el completo, sabremos que es imposible conseguirlo ¿Qué os parece?

—¡Bien! —gritó Ula como si se hubiese enterado perfectamente de todo. Los demás sonrieron como aquellos ministros ante el traje nuevo del emperador…

—Yo quiero pintar los huevos de colores Mati —dijo inmeditamente Ot.

—Vale —dijo ella —Vamos a pintar de amarillo la arista que une a Ot con los huevos para indicar que esa pareja ya la tenemos asignada.

—Qué morro… —murmuró Germán para añadir después sonriendo—Bueno, no pasa nada.

—¿Puedo escribir yo las pistas del tesoro que ya sé escribir con minúsculas? —preguntó Elio poniéndose de puntillas para parecer más mayor.

—Muy bien —aceptó Mati —Pintamos de amarillo la arista que une a Elio con las pistas.

—¡Mati, Mati! —se escuchó la vocecita de Gonzalo —¡Ponme a mí para ayudar a adornar la tarta con chuches!

—Ahora, de amarillo la arista que une a gonzalo con la tarta.

—Yo soy muy bueno llenando globos de agua… —dejó caer Jose — Mis primos de Almería siempre quieren que yo se los llene…

—Entendido —dijo Mati —En amarillo la arista que une a Jose con los globos…

—¿Me puedes asignar a mí los caramelos Mati? —pidió Sal —Me gustaría poner una sorpresita en cada bolsita…

—¿Qué, qué? —preguntó Ula curiosona.

—Ula, ¡es una sorpresita! —intervino Ven y Ula retorció un poco su boquita.

—De acuerdo —intervino la pelirroja —Ponemos en amarillo la arista que une a Sal con los caramelos que aún estaban libres…

— Ya no podemos seguir —anunció Mati —Porque sólo quedan sin tareas Ula y Germán, pero las tareas que ellos han pedido ya están asignadas a otros.

—¡Jo no jugo! (¡No juego!) —gritó espontáneamente Ula.

—No te enfades Ula —la consoló Germán —Tú y yo jugaremos con Pepita, ¿vale?

—No, no, no —intervino Ven —Tienen que trabajar todos, es mi fiesta…

—Tranquilos todos —dijo Mati —Os voy a enseñar un método para mejorar la asignación de tareas si se puede, ¿vale?

Los niños asintieron todos callados, Gauss resopló viendo cómo se calmaba por momentos la tormenta.

—¿Os acordáis de cómo se coloreaban los vértices de un grafo? —les preguntó la gafotas.

—Sí —respondió rápidamente Ven —Se colorean los vértices pero no pueden estar unidos vértices del mismo color. Y sólo se necesitan 4 colores como máximo, ¿verdad Mati?

—Si el grafo es plano, Ven —corrigió Sal —pero éste tiene muchos cruces…

—Huy —interrumpió Mati inmediatamente —No, no hace falta estudiar si el grafo es plano o no, es más fácil, mucho más fácil. Pero Sal, el hecho de que un grafo esté dibujado con muchos cruces no significa que no sea plano. A lo mejor sólo hay que dibujar el mismo grafo de otra forma. Mira, os pongo un ejemplo sencillito.

Mati dibujó dos grafos en su pizarra

—Estos dos grafos son el mismo —les dijo —Sólo que están dibujados de diferente forma. Como en el dibujo de la derecha no se cruzan las aristas, decimos que el grafo es plano, que se puede dibujar sin cruces —Mati continuó —Nuestro grafo también es plano…

—Sí, hombre… —bufó Jose.

—Sí, lo es —ratificó Mati —Os dejo que penséis cómo dibujarlo plano, sin cruces, pero mañana después de la fiesta.

—¡Mola! —se alegró Ot.

—Como os decía —continuó la pelirroja —Vamos a colorear los vértices de nuestro grafo de tareas, ¿cuántos colores necesitaremos?

—Cuatro —dijo Germán con sonrisa pícara —Se te ha escapado que es plano y como los planos necesitan cuatro colores…

—Cómo máximo, Germán —puntualizó Sal —como máximo.

—Efectivamente —añadió Mati —Como mucho serán cuatro colores, pero vamos a fijarnos un poco en este grafo.

Todos los niños arrugaron la nariz y el ceño y se pusieron a mirar fijamente la pizarra de Mati. Gauss también.

—Fijaos —empezó a decir Mati —Todos los vértices correspondientes a los niños pueden ser del mismo color, ¿verdad?

Los niños relajaron sus caritas y se giraron a mirar todos a Mati. Bueno, todos no, Gonzalo seguía con su expresión de concentrado, no quería despistarse…

—¡Toma, claro! —dijo Ven enseguida —Porque ningún niño está unido con ningún niño, las aristas siempre unen a un niño con una tarea.

—¡Rojo, por favor, Mati! —pidió Elio.

—Muy bien —dio ella —Los vértices correspondientes a los nombres de los niños los pintamos en rojo….

—¡Ya está! —gritó Sal saliendo de su ensimismamiento y asustando a Gauss —Todas las tareas también pueden tener el mismo color porque ninguna tarea se une con ninguna tarea ¡Sólo se necesitan dos colores, Mati!

—Las tareas en azul, por favor, Mati —pidió Ot poniendo caritas.

—Muy bien chicos —Mati sonreía feliz —Efectivamente, sólo se necesitan dos colores para colorear los vértices de nuestro grafo. Vamos a pintarlos en rojo y azul como han pedido Elio y Ot.

—A estos grafos en los que podemos colorear los vértices con sólo 2 colores se les llama grafo bipartitos. En éstos, los vértices están agrupados en 2 conjuntos separados, el rojo y el azul en nuestro caso, cuyos elementos no se relacionan entre ellos —les explicó la pelirroja —Ahora vamos a organizar un baile…

—-Jo sóc la millor ballarina del món (Yo soy la mejor bailarina del mundo) —gritó nuestra Ula y dio una vuelta de puntillas dejando a todos adorar su maravilloso tutú.

—¿Un baile ahora, Mati? —se quejó Ven y añadió murmurando —Ya verás, al final no nos dará tiempo a organizarlo todo…

—Sí, Ven, un baile —respondió Mati —Pero este baile servirá para la asignación de tareas y eso permitirá una mejor organización y, por lo tanto, nos dará tiempo a todo.

—¡Venga, el baile! —pidió Elio.

—Os cuento —empezó la gafotas —Vamos a suponer que las aristas del grafo nos indica con que puntos azules querrían bailar cada uno de los puntos rojos, y vamos a tratar de emparejarlos todos. Nos fijamos en un punto rojo que no esté emparejado…

—El de la mejor bailarina del mundo… —dijo Ot sonriendo pícaro, Ula arrugó toda su carita.

—Eso es, nos fijamos en Ula —dijo Mati —Ula sólo quería bailar con Caramelos y le pregunta: ¿Quieres bailar Caramelos?. Los pintamos aquí al lado unidos con línea blanca como está en el grafo.

—Pero Caramelos responde: No puedo, yo bailaré con Sal —continuó Mati —Pintamos a Sal unido a Caramelos con una línea amarilla, igual que está en nuestro grafo.

—Entonces nuestro punto rojo, Ula —siguió —Pregunta a Sal si no le importa cambiar de pareja, eligiendo a otra de las que él había elegido. Y Sal dice: Bueno, preguntaré a los otras 3 que había elegido, a ver si queda alguno libre y Sal le pregunta a Globos, Magia y Tarta.

—Primero le pregunta a Globos —Mati tenía a todos pendiente de su baile —Pero Globos le dice que ya está emparejado con Jose.

—Entonces, —dijo —le pregunta a Magia y ¡tachán! Magia está libre.

—¡Bien! —gritó Ula de pronto.

—Fijaos en el dibujo que tenemos a la derecha de nuestro grafo —señaló Mati —tenemos un camino, que empieza en Ula y termina en Magia, donde los colores de las aristas se van alternando entre blanco y amarillo, que empieza y termina con aristas blancas. Es lo que llamamos una camino alternado. Pues bien, si existe camino alternado, que empieza y termina en aristas blancas (sin emparejar), se puede mejorar el emparejamiento.

—¿Cómo? —preguntó Sal impaciente.

—Muy fácilmente —respondió Mati —Vamos a intercambiar los colores amarillo y blanco en las aristas.

—Ahora hacemos esos cambios de color en nuestro grafo…

—¡Ya tengo tarea! —gritó Ula alegremente y volvió a girar de puntillas.

—Es verdad, Mati —dijo Jose —Hemos emparejado a uno más…

—¡Toma, toma, toma! ¡Cómo mola! —gritó Ven.

—Sí —dijo Gonzalo y añadió con penita —Ya sólo falta tarea para mi hermano…

—Eso es —afirmó Mati —Vamos a intentar buscar un camino alternado empezando ahora con Germán que es el único punto rojo que no tiene pareja. Germán le preguntará a los dos que él había elegido en principio: Huevos y Caramelos.

—Pero Caramelos —siguió la gafotas —le dice que él está emparejado con Ot …

—Germán le pregunta a Ot si le importa cambiar de pareja —continuó —Pero Ot le responde que su otra alternativa era Caramelos que ya está emparejado con Ula. Y ella no puede cambiar de pareja porque sólo había elegido a Caramelos.

—¿Qué pasa ahora Mati? —preguntó Germán angustiado.

—Pues que no existe el camino alternado —aceptó ésta con tristeza —y no podemos mejorar el emparejamiento, era el mejor que se podía conseguir, a éstos les llamamos emparejamientos máximos.

—¿No podemos emparejarlos a todos? —era Ven el que se angustiaba ahora.

—No —confirmó Mati —Para este grafo bipartito no existe emparejamiento completo, cualquier emparejamiento dejará a un niño sin tarea.

Los niños se quedaron todos muy serios mirando la pizarra de Mati que continuó:

—Mirad, vamos a quedarnos con el grafo correspondiente sólo a las peticiones de Gemán, Ot y Ula.

—Cómo véis —les dijo —tenemos 3 niños que han pedido sólo 2 tareas distintas, eso hace imposible el emparejamiento completo.

—Es verdad… —dijo Jose.

—Para que exista el emparejamiento completo —les contó —cualquier subconjunto de personas del primer grupo debe elegir como mínimo el mismo número de tareas del segundo grupo, es la conocida condición de Hall.

—Lo sabía… —dijo Ven con resignación —No podremos prepararlo todo…

—Que sí, Ven —le respondió Germán mientras le rodeaba con su brazo —Yo me encargo de decorar las galletas, que me gusta mucho.

—¿En serio? —preguntó Ven con los ojos brillantes —No lo habías pedido.

—Se me olvidó —Germán guiñó un ojo a Ven.

—En ese caso —intervino Mati —gracias a la teoría de grafos y a Germán tenemos resuelto nuestro problema.

—¡Todos a sus puestos! —gritó Sal —¡a trabajar!

—¡Sí! —gritaron los demás.

—¿Cuántos niños vienen Ven? —preguntó Mati.

—28.

—¿¿28?? —repitió Mati asombrada.

—Sí, ya sabes —trató de explicar Ven —Es verano y muchos están de vacaciones…

FIN

Bueno, bueno, bueno… Éste es nuestro último capítulo hasta que volvamos en Septiembre. Espero que os haya gustado y como vamos a estar un mes sin vernos, os voy a dejar propuestos unos retos, ¿os apetece?

El primero de ellos tiene que ver con algo que pasó en nuestra mateaventura de hoy, cuando Sal insinuó que el grafo que representaba las preferencias de los niños por las tareas en la fiesta, vamos éste

no era plano. Un grafo es plano si se puede dibujar sin cruces entre las aristas. En el dibujo anterior hay muchos cruces, sí, pero eso no significa que no sea plano. De hecho, como ya les he dicho a nuestros amigos, ese grafo es plano. Ahora viene el primer reto, ¿eres capaz de dibujarlo sin que se corten las aristas? El truco está en coloca de forma apropiada los vértices ¿Qué? ¿Te atreves? Inténtalo, pero si no te sale y te desesperas, puedes ver una posible solución aquí.

El segundo reto tiene que ver, lógicamente, con emparejamientos ¿Puedes dar un emparejamiento completo para este grafo? Puedes empezar con uno cualquiera, luego intentar mejorarlo con caminos alternados… ya sabes…

Y por último, si te doy el grafo de la siguiente figura donde se han pintado de amarillo las aristas de un emparejamiento, ¿puedes completarlo hasta un emparejamiento completo buscando un camino alternado que empiece en el 2?

Ya me contaréis en los comentarios vuestras respuestas.

Una cosa más, en la mateaventura de hoy se habló de coloreado de grafos. si te interesó el tema, puedes leer más en esta entrada que Clara publicó en Amazings.

Eso es todo por ahora. Nos vamos de vacaciones hasta Septiembre. Deseamos que descanséis, que hagáis mates allá por donde vayáis y sobre todo, que estéis de vuelta por aquí después de Agosto.

Hasta pronto

MATI