5. Coloración de grafos

1. El problema del mapa de los cuatro colores

Imagen de XalD en Wikimedia Commons. *Mapa mundial con 4 colores*. (CC BY-NC-SA)

La respuesta a esta pregunta es que sí, sí se puede. La demostración de esta afirmación se conoce como Teorema de los cuatro colores.

El Teorema de los cuatro colores fue propuesto por primera vez en 1852 por Francis Guthrie y fue probado finalmente por Kenneth Appel y Wolfgang Haken en 1976. Su demostración es notable porque fue una de las primeras en las que se utilizó un ordenador para verificar una gran cantidad de casos particulares, lo que generó cierta controversia sobre la naturaleza de la prueba en la comunidad matemática. Sin embargo, la demostración ha sido confirmada y aceptada desde entonces.

El vínculo entre este teorema y la teoría de grafos es fundamental y se establece a través de la representación de mapas como grafos planos. Esta conexión permite aplicar conceptos de la teoría de grafos, en particular la coloración de vértices, para resolver problemas de coloración de mapas.

Pero, ¿cómo se relacionan ambos conceptos? Veamoslo.

Representación de mapas como grafos

Vértices del Grafo: cada región del mapa se representa como un vértice en el grafo. Por lo tanto, si un mapa tiene $N$ regiones, el grafo correspondiente tendrá $N$ vértices.
Aristas del Grafo: dos vértices en el grafo están conectados por una arista si las regiones correspondientes son adyacentes en el mapa, es decir, si comparten una frontera común. Esto significa que el grafo captura la estructura de adyacencia de las regiones en el mapa.

Coloración de Vértices

La tarea de colorear el mapa de manera que ninguna región adyacente comparta el mismo color se traduce en el problema de coloración de vértices en el grafo correspondiente. En este contexto, un "color" es una etiqueta que se asigna a cada vértice (región), y la regla es que vértices conectados (regiones adyacentes) no pueden tener la misma etiqueta (color).

2. Coloración de vértices de un grafo

La coloración de grafos es una forma de asignar colores a los elementos de un grafo, como sus vértices, aristas o caras, siguiendo ciertas reglas o restricciones.

La coloración de vértices es el tipo más común de coloración de grafos. El objetivo es colorear los vértices de un grafo de tal manera que no haya dos vértices adyacentes (conectados por una arista) que tengan el mismo color. El número mínimo de colores necesarios para lograr esto en un grafo se denomina su número cromático.

Definición: asignación de colores a los vértices de un grafo de tal manera que ningún par de vértices adyacentes (conectados directamente por una arista) comparta el mismo color.
Objetivo: minimizar el número de colores utilizados, siendo el ideal el número cromático del grafo, que es el mínimo número de colores necesarios para lograr una coloración válida.

A continuación, se muestra un grafo cuyo número cromático es 3, con los vértices coloreados utilizando tres colores distintos (rojo, verde y azul). Como se puede observar, ningún vértice adyacente comparte el mismo color, cumpliendo con las reglas de la coloración de vértices en teoría de grafos.

Imagen de elaboración propia. *Grafo coloreado.* (CC BY-NC-SA)

Estas son algunas de sus aplicaciones:

Planificación de horarios: evitar que cursos con alumnado en común se programen al mismo tiempo.
Mapas políticos: colorear países o regiones de manera que países limítrofes no compartan el mismo color, facilitando la diferenciación visual.
Asignación de frecuencias de radio: asegurar que estaciones de radio de telefonía móvil adyacentes usen diferentes frecuencias para evitar interferencias.

3. Ejemplo resuelto

Un centro educativo de secundaria está planificando los horarios de los exámenes finales de recuperación para el final de curso. Debido a que algunos alumnos están inscritos en múltiples asignaturas, el centro quiere asegurarse de que no haya conflictos de horarios para estos alumnos. El objetivo es organizar los exámenes de manera que se utilice el menor número de franjas horarias posible, garantizando que ningún alumno tenga dos exámenes al mismo tiempo.

Estas son las asignaturas que deben ser recuperadas :

Matemáticas (Mat)
Ciencias (Cien)
Historia (Hist)
Literatura (Lit)
Arte (Art)
Educación Física (EF)

Estas son las inscripciones de los alumnos:

Alumnos que deben recuperar Matemáticas y Ciencias.
Alumnos que deben recuperar Ciencias e Historia.
Alumnos que deben recuperar Historia y Literatura.
Alumnos que deben recuperar Literatura y Arte.
Alumnos que deben recuperar Ciencias y Educación Física.
Alumnos que deben recuperar Matemáticas y Historia.
Alumnos que deben recuperar Arte y EF.

Respuesta al problema.

1. Construcción del Grafo.
Cada asignatura se representa como un vértice en el grafo. Una arista conecta dos vértices si existe al menos un alumno inscrito en ambas asignaturas, lo que implica un conflicto si estos exámenes se programan en el mismo horario.

2. Representación del Grafo.

Vértices: Mat, Cien, Hist, Lit, Art, EF.
Aristas:
- Mat - Cien (Alumnos que deben recuperar en ambas asignaturas)
- Cien - Hist (Alumnos que deben recuperar en ambas asignaturas)
- Hist - Lit (Alumnos que deben recuperar en ambas asignaturas)
- Lit - Art (Alumnos que deben recuperar en ambas asignaturas)
- Cien - EF (Alumnos que deben recuperar en ambas asignaturas)
- Mat - Hist (Alumnos que deben recuperar en ambas asignaturas)
- Art - EF (Alumnos que deben recuperar en ambas asignaturas)

Con esta información, podemos crear el grafo correspondiente:

Imagen de elaboración propia. *Grafo horario.* (CC BY-NC-SA)

La información anterior se organiza en la siguiente tabla, que se divide en dos columnas. La primera columna lista todos los vértices, y la segunda detalla los vértices adyacentes a cada uno de ellos.

Imagen de elaboración propia. *Tabla de adyacencia.* (CC BY-NC-SA)

3. Coloración de vértices.

El siguiente paso sería aplicar la coloración de vértices a este grafo para determinar el número mínimo de franjas horarias necesarias para programar todos los exámenes sin conflictos. Este proceso involucra asignar colores (en este contexto, franjas horarias) a cada vértice de manera que ningún vértice adyacente (asignaturas con exámenes conflictivos) comparta el mismo color.

Al aplicar la coloración de vértices al grafo, cada color representa una franja horaria única. Asignar un color diferente a cada vértice adyacente (asignatura) asegura que no se programen dos exámenes con conflictos de inscripción en la misma franja horaria. En otras palabras, asignaturas que comparten alumnos no recibirán el mismo color.

Aquí tienes el grafo de organización de horarios de exámenes con los vértices coloreados, representando una posible asignación de franjas horarias a cada asignatura. Se han utilizado tres colores (rojo, verde, azul), lo que refleja que el número cromático del grafo es 3. Esto significa que podemos organizar todos los exámenes usando solo tres franjas horarias diferentes, asegurando que ningún alumno tenga exámenes simultáneos en asignaturas distintas. Cada color representa una franja horaria distinta en la que se pueden programar los exámenes sin conflictos.

Imagen de elaboración propia. *Grafo horario coloreado.*
(CC BY-NC-SA)

En las siguiente tabla se muestran la organización de exámenes por franja horaria.

Imagen de elaboración propia. *Franjas horarias.* (CC BY-NC-SA)

4. Algoritmo de coloración de vértices

En el ejemplo anterior hemos visto la utilidad que tiene la coloración de vértices de un grafo. Existen varios algoritmos para la coloración de vértices, siendo el algoritmo de Welsh-Powell uno de los más simples. Su objetivo principal es minimizar el número de colores usados, conocido como el número cromático del grafo.

Pasos del Algoritmo de Welsh-Powell

Ordenar vértices por grado descendente.
- Enumera todos los vértices del grafo y ordénalos según su grado (número de aristas que los conectan con otros vértices) en orden descendente.
Inicialización.
- Empieza con el primer color disponible. Este será asignado a uno o más vértices del grafo.
- Inicializa una lista o conjunto para llevar el registro de los vértices ya coloreados.
Asignación de colores.
- Comenzando con el vértice de mayor grado y siguiendo el orden establecido, asigna el color actual al vértice si y solo si no tiene adyacentes (vecinos) ya coloreados con ese mismo color.
- Repite este proceso para cada vértice en el orden determinado, pasando al siguiente color disponible tan pronto como encuentres un vértice que no pueda ser coloreado con el color actual debido a una restricción de adyacencia.
Iterar.
- Continúa el proceso iterativamente, asignando colores a los vértices restantes, siempre siguiendo el orden preestablecido y respetando la regla de que vértices adyacentes no pueden compartir el mismo color.
- Avanza al siguiente color tan pronto como encuentres un vértice que no cumpla con las condiciones para ser coloreado con el color actual.
Finalización.
- El algoritmo termina cuando todos los vértices han sido coloreados.

Imagen de elaboración propia. *Diagrama del Algoritmo.*
(CC BY-NC-SA)

El algoritmo de Welsh-Powell es especialmente útil en problemas de optimización como la organización de horarios y la asignación de recursos, donde se busca una solución práctica que minimice el solapamiento o la interferencia.

Aunque este algoritmo es muy eficiente, no garantiza encontrar el número cromático del grafo (es decir, el mínimo número de colores necesario para una coloración válida).

Ejemplo.

Para aplicar el algoritmo de Welsh-Powell al problema de organización de horarios de exámenes del problema anterior y obtener el grafo coloreado mostrado anteriormente, seguimos estos pasos:

Paso 1: Ordenar los vértices por Grado Descendente.
- Primero, ordenamos las asignaturas (vértices) según el número de conflictos de inscripción (grado en el grafo), de mayor a menor. Esto nos da la prioridad para asignar colores, empezando por las asignaturas con más conflictos.
- Grados de los vértices: (antes de las inscripciones adicionales) Ciencias (3 conflictos) - Con Matemáticas, Historia, y Educación Física.
- Los demás vértices tienen 3 o menos conflictos en este ejemplo simplificado.
Paso 2: Asignar Colores a los Vértices.
- Comenzamos con el vértice de mayor grado: Ciencias o Historia y le asignamos el primer color disponible. Elegimos Ciencias para asignar el primer color. Luego, seguimos el orden descendente de los vértices, asignando a cada uno el menor número de color que no haya sido asignado a sus vértices adyacentes.
- Asignación de Colores: (siguiendo el ejemplo con inscripciones adicionales) Ciencias recibe el color 1 (azul).
- Matemáticas, adyacente a Ciencias y Historia, recibe el color siguiente disponible, color 2 (rojo).
- Historia, adyacente a Ciencias y Matemáticas, recibe el color 3 (verde).
- Seguimos este proceso para las demás asignaturas, asegurando que asignaturas adyacentes no compartan colores.
Paso 3: Continuar hasta colorear todos los vértices.
- Continuamos asignando colores a cada asignatura, siguiendo el orden establecido y respetando las restricciones de adyacencia, hasta que todas las asignaturas estén coloreadas.
- Arte y Educación Física son coloreados considerando sus adyacencias y los colores ya asignados.
Paso 4: Resultado.
- El resultado es un grafo donde cada asignatura (vértice) está asignada a una franja horaria (color) de tal manera que no hay conflictos de horarios para los estudiantes. En nuestro ejemplo simplificado, logramos asignar los exámenes a tres franjas horarias diferentes, lo que corresponde al número cromático del grafo.

Conclusión:
El algoritmo de Welsh-Powell nos permite organizar eficientemente los horarios de exámenes, minimizando el número de franjas horarias necesarias y evitando conflictos de horario para el alumnado. Este método sistemático y ordenado asegura una asignación de colores (horarios) que respeta todas las restricciones de inscripción, demostrando su utilidad en la planificación académica.

Imagen de elaboración propia. *Grafo franjas horarias.* (CC BY-NC-SA)

5. Resuelve aplicando coloración de grafos

Problema 1: Asignación de aulas universitarias

Imagen de elaboración propia generada con DALL-e 3. *Campus universitario.* (CC BY-NC-SA)

Una universidad debe asignar aulas y franjas horarias para las clases de siete asignaturas diferentes del próximo semestre. La dificultad radica en que algunos alumnos están matriculados en múltiples asignaturas, lo que podría generar coincidencias en los horarios si no se planifica cuidadosamente. El objetivo es utilizar la coloración de vértices para asignar horarios a las clases de tal manera que se eviten conflictos para el alumnado y, al mismo tiempo, se optimice el uso de las aulas disponibles.

Las asignaturas son: Matemáticas (Mat), Física (Fis), Química (Qui), Historia (His), Literatura (Lit), Filosofía (Fil) y Biología (Bio)

Las matriculaciones del alumnado han sido:

Existen alumnos matriculados simultáneamente en Matemáticas y Física.
Algunos alumnos están matriculados en Química y Biología.
Hay estudiantes que toman tanto Historia como Literatura.
Un grupo de alumnos está inscrito en Filosofía y Literatura.
También hay alumnos que comparten matrícula entre Física y Química.
Un número menor de estudiantes está matriculado en Biología y Matemáticas.
Existen alumnos matriculados simultáneamente en Física (Fis) y Literatura.

Se trata de organizar las clases en el menor número de franjas horarias posibles para las clases, de tal manera que se eviten conflictos para el alumnado.

Crea el grafo para el problema de asignación de aulas universitarias, basado en las siete asignaturas y las matriculaciones de los alumnos que podrían generar coincidencias de horarios (dos asignaturas adyacentes no se pueden impartir en la misma franja horaria)
Colorea el grafo para determinar el número mínimo de franjas horarias necesarias para realizar todas las clases sin conflictos de horario para los alumnos, optimizando el uso de aulas de la universidad.
Muestra en una tabla las diferentes franjas horarias para las clases de las siete asignaturas.
¿Cuántas aulas son necesarias para impartir todas las asignaturas?

Respuesta

1. Grafo de asignación de aulas universitarias. Dos asignaturas conectadas por una arista significa que no se pueden impartir en la misma franja horaria, pues existen alumnos que se han matriculado en ambas materias.

Imagen de elaboración propia. *Grafo de aulas universitarias.* (CC BY-NC-SA)

2. Esta coloración demuestra que el grafo puede ser considerado bipartito, lo que significa que es posible organizar todas las clases en solo dos franjas horarias sin generar conflictos de horarios para los alumnos.

3. Esta es la tabla que organiza las diferentes franjas horarias para las clases, utilizando solo dos colores para la asignación, lo que refleja una estructura bipartita.

Imagen de elaboración propia. *Franjas horarias y aulas.* (CC BY-NC-SA)

4. Dado que en la segunda franja horaria se imparten cuatro asignaturas, necesitaríamos 4 aulas en total para poder impartir todas las asignaturas sin conflictos. Esto permite un uso eficiente del espacio físico disponible, alternando las aulas entre las franjas horarias para acomodar todas las clases programadas.

Problema 2. Coloración del mapa de las provincias de Andalucía

Desarrolla un esquema de coloración para el mapa de las provincias de Andalucía que utilice el menor número de colores posible. El objetivo es asignar un color a cada provincia de tal manera que provincias limítrofes (aquellas que comparten frontera) no compartan el mismo color.

Respuesta

Pasos a Seguir:

Construcción del Grafo de Provincias Limítrofes:
- Creamos un grafo donde los vértices representen las ocho provincias de Andalucía: Huelva, Sevilla, Cádiz, Córdoba, Málaga, Granada, Jaén y Almería.
- Conectamos los vértices con aristas que simbolizan la contigüidad entre provincias.

Imagen de elaboración propia. *Grafo provincias de Andalucía.* (CC BY-NC-SA)

Coloración del grafo con el Algoritmo de Welsh-Powell:
- Aplicamos el algoritmo de Welsh-Powell para realizar una coloración de vértices en el grafo.
- Este método comienza coloreando el nodo con el mayor grado y luego asigna colores a los vértices restantes, asegurando que cada vértice adyacente tenga un color diferente.

Aplicación de colores al mapa político de Andalucía:
- Tras obtener la coloración óptima del grafo, transferir esa coloración al mapa político de Andalucía.
- Cada provincia en el mapa se coloreará con el color correspondiente a su vértice en el grafo, asegurando que dos provincias adyacentes no tengan el mismo color.

Imagen de elaboración propia. *Mapa coloreado de las provincias de Andalucía.* (CC BY-NC-SA)

El resultado final será un mapa de Andalucía colorido que cumple con las reglas de la coloración de grafos, utilizando la menor cantidad de colores posible (número cromático 3), lo que proporcionará una representación visualmente clara y diferenciada de cada provincia. Este mapa puede ser útil en diversas aplicaciones, desde educación hasta planificación regional.

Problema 3. Optimización de espacio en centro de conservación de peces tropicales

Un centro de conservación de peces tropicales necesita reorganizar sus acuarios después de recibir varias especies nuevas. Para asegurar la supervivencia de todas las especies, se requiere evitar que los depredadores y sus presas habiten el mismo espacio.

Datos Específicos:

El pez ángel (1) se come al pez mariposa (4) y al pez damisela (5).
El pez cirujano (2) se come al pez payaso (6) y al pez gobio (7).
El pez león (3) se come al pez escorpión (8) y al pez mandarín (9).
El pez mariposa (4) es presa del pez ángel (1) y del pez cardenal (10).
El pez damisela (5) es presa del pez ángel (1) y se come al pez cardenal (10).
El pez payaso (6) es presa del pez cirujano (2) y se come al blénido (11).
El pez gobio (7) es presa del pez cirujano (2) y se come al pez neón (12).
El pez escorpión (8) es presa del pez león (3) y se come al pez trompeta (13).
El pez mandarín (9) es presa del pez león (3) y se come al pez cirujano (2).
El pez cardenal (10) es presa del pez damisela (5) y se come al pez mariposa (4).

Crea un grafo de coloración que muestre las interacciones depredador-presa y calcula el número mínimo de acuarios que el centro necesita para para mantener a todas las especies en venta sin riesgo de depredación.

Respuesta

Para crear el grafo que representa las relaciones depredador-presa entre las especies de peces tropicales, debemos establecer:

Vértices (Nodos):
- Cada vértice del grafo representa una especie de pez tropical única, y los numeramos de 1 a 13 para identificar cada especie de pez diferente. Por ejemplo, el vértice "1" representa al pez ángel, el vértice "2" al pez cirujano, y así sucesivamente.
Aristas (Conexiones):
- Las aristas conectan dos vértices y representan la relación depredador-presa entre las especies. Si una especie de pez (por ejemplo, el pez ángel) se come a otra especie (como el pez mariposa), entonces se dibuja una arista que conecta los vértices correspondientes a estas dos especies.

A continuación, se muestra el grafo correspondiente. Los nodos representan las diferentes especies de peces, y están coloreados aplicando el algoritmo de Welsh-Powell. De esta manera se evita que especies depredadoras y presas compartan el mismo color (acuario). Esta coloración facilita la asignación de especies a acuarios de manera que se minimiza el número de acuarios necesarios y se evita que los peces depredadores estén con sus presas.

Imagen de elaboración propia. *Grafo acuarios.* (CC BY-NC-SA)

Como se observa, el grafo es bipartito, ya que es posible dividir el conjunto de sus vértices en dos grupos, de tal manera que no existan aristas que conecten vértices dentro del mismo grupo. En el contexto del problema, esto implica que podemos organizar las especies de peces en dos acuarios distintos sin que haya riesgo de que los peces depredadores estén junto a sus presas.

6. Importante

El problema del mapa de los cuatro colores

Dado cualquier mapa plano dividido en regiones (como los países en un mapa mundial), ¿es posible colorear las regiones con no más de cuatro colores de tal manera que ninguna región comparta el mismo color con una región adyacente (es decir, aquellas que tienen una frontera común)?. La respuesta a esta pregunta es que sí, sí se puede. La demostración de esta afirmación se conoce como Teorema de los cuatro colores.