Distribuir clases, turnos de trabajo o sesiones de conferencia sin que se pisen entre sí es uno de esos problemas que parecen sencillos sobre el papel pero que escalan rápidamente en complejidad. Basta con que un alumno curse tres asignaturas que coinciden en la misma franja para que el horario entero haya de reorganizarse. Este tipo de restricciones encadenadas convierten la asignación de horarios en un problema NP-completo en el caso general, lo que obliga a recurrir a heurísticas y algoritmos aproximados cuando el número de variables crece.
Una de las técnicas más eficaces para abordarlo es la coloración de grafos: representamos cada asignatura o evento como un vértice y trazamos una arista entre dos vértices cuando sus participantes se solapan. Encontrar un horario válido equivale entonces a asignar colores a los vértices de modo que ningún par de adyacentes comparta color. Cada color representa una franja horaria distinta y el número de colores necesarios es el número mínimo de franjas que hacen falta.
Modelado como grafo
El punto de partida es un grafo bipartito en el que un lado recoge a los alumnos y el otro a las asignaturas. Una arista entre alumno y asignatura indica que ese alumno está matriculado en ella. A partir de ahí, el algoritmo anadeAristasAsignaturas construye el grafo de conflictos: dos asignaturas quedan unidas si hay al menos un alumno común, porque no pueden coincidir en la misma hora.
Considera este ejemplo concreto. El alumno 1 está matriculado en As-1, As-2 y As-3, así que entre estas tres asignaturas se añaden las aristas (As-1, As-2), (As-2, As-3) y (As-1, As-3). El alumno 2 cursa As-2 y As-3, pero esa arista ya existe. El alumno 4 introduce una arista nueva al cursar As-3 y As-4 a la vez. Los demás alumnos no aportan relaciones nuevas. El resultado es el grafo de conflictos:
Para visualizarlo como texto, la estructura de adyacencias queda así:
As-1 --- As-2 As-1 --- As-3 As-2 --- As-3 As-3 --- As-4
Cada arista prohíbe que las dos asignaturas que une compartan franja horaria.
El algoritmo greedy de coloración de vértices
El algoritmo voraz de coloración de vértices recorre los vértices en orden y asigna a cada uno el menor color disponible que no use ninguno de sus vecinos. No garantiza el óptimo global, pero en la práctica obtiene resultados muy razonables con un coste computacional bajo.
Veamos el proceso paso a paso con el grafo del ejemplo:
Paso 1 Se procesa As-1. Ningún vecino tiene color asignado aún, así que se le da el color 1 (azul).
Paso 2 Se procesa As-2. Su vecino As-1 ya tiene color 1, así que se le asigna el color 2 (verde).
Paso 3 Se procesa As-3. Sus vecinos tienen color 1 (As-1) y color 2 (As-2), así que se le asigna el color 3 (amarillo).
Paso 4 Se procesa As-4. Su único vecino es As-3 con color 3, de modo que puede usar de nuevo el color 1 (azul).
El resultado en forma de tabla:
Franja horaria | Color | Asignaturas |
Hora 1 | Azul | As-1 y As-4 |
Hora 2 | Verde | As-2 |
Hora 3 | Amarillo | As-3 |
Con solo tres franjas quedan cubiertas las cuatro asignaturas sin que ningún alumno tenga que elegir entre dos clases simultáneas. El número de colores usados es el número cromático del grafo, que aquí vale 3.
Implementación en Python
A continuación se muestra una implementación limpia del algoritmo en Python. El grafo se representa como un diccionario de listas de adyacencia y la función colorear_grafo aplica la heurística voraz:
def colorear_grafo(adyacencias: dict[str, list[str]]) -> dict[str, int]:
"""
Coloración voraz de vértices.
Devuelve un diccionario {vertice: color} donde color >= 1.
"""
colores: dict[str, int] = {}
for vertice in adyacencias:
# Colores ya usados por los vecinos
colores_vecinos = {colores[v] for v in adyacencias[vertice] if v in colores}
# Asignar el menor color positivo que no esté ocupado
color = 1
while color in colores_vecinos:
color += 1
colores[vertice] = color
return colores
# --- Ejemplo del artículo ---
grafo = {
"As-1": ["As-2", "As-3"],
"As-2": ["As-1", "As-3"],
"As-3": ["As-1", "As-2", "As-4"],
"As-4": ["As-3"],
}
asignacion = colorear_grafo(grafo)
nombres_color = {1: "Azul (Hora 1)", 2: "Verde (Hora 2)", 3: "Amarillo (Hora 3)"}
for asignatura, color in asignacion.items():
print(f"{asignatura}: {nombres_color.get(color, f'Color {color}')}")
La salida del programa reproduce exactamente el resultado del ejemplo visual:
As-1: Azul (Hora 1) As-2: Verde (Hora 2) As-3: Amarillo (Hora 3) As-4: Azul (Hora 1)
Para proyectos reales con grafos grandes, la librería NetworkX incluye varios algoritmos de coloración, entre ellos la estrategia greedy con distintos órdenes de procesado (nx.coloring.greedy_color), lo que permite comparar resultados y ajustar la heurística según el caso concreto.
La aplicación Java original
La versión interactiva desarrollada inicialmente era una aplicación de escritorio en Java con interfaz Swing. Aunque los applets de Java llevan años sin funcionar en los navegadores actuales, las capturas muestran con claridad cómo se introducían los datos y qué aspecto tenía la salida.
La pantalla de Asignaturas permitía añadir cada materia con su identificador y nombre:
La pantalla de Alumnos recogía el nombre y DNI de cada estudiante y permitía matricularle en las asignaturas disponibles. Al seleccionar un alumno, la lista mostraba de inmediato las materias en que estaba inscrito:
Finalmente, el botón Crear Horarios lanzaba el algoritmo y mostraba en una tabla las franjas necesarias y las asignaturas asignadas a cada una:
La aplicación admitía cualquier número de alumnos y asignaturas; el tiempo de cómputo crecía con el tamaño del grafo, pero para escenarios universitarios típicos la respuesta era prácticamente inmediata.
Si quieres ver algoritmos de grafos y otras estructuras de datos en acción con animaciones interactivas, echa un vistazo a Algorithm Visualizer. Y si te interesa automatizar procesos con Python, el artículo sobre automatización con Python y RPA ofrece un buen punto de partida.
Imagen: Pexels / Google DeepMind