🚀 Introducción: Optimización de recursos con Coloración de Grafos

¿Cómo se organizan los horarios de los exámenes finales en un instituto para que ningún alumno tenga dos exámenes a la misma hora? ¿Cómo se asignan las frecuencias de las antenas de telefonía móvil para que las señales vecinas no interfieran entre sí?

Para resolver estos problemas de organización y evitar "conflictos", las matemáticas utilizan la coloración de grafos. En este modelo:

• Los nodos representan las actividades que queremos planificar (talleres, asignaturas, antenas).

• Las aristas (líneas) conectan aquellas actividades que no pueden coincidir bajo ningún concepto (porque comparten alumnos, se hacen en el mismo espacio o se solapan en el espacio).

El objetivo del algoritmo es asignar un "color" (que representa un día, una hora o una frecuencia) a cada nodo con una condición inquebrantable: dos nodos conectados por una línea no pueden tener el mismo color. Además, para ahorrar costes o tiempo, debemos encontrar el número cromático, que es la cantidad mínima absoluta de colores necesarios para pintar todo el grafo de forma segura.

Hoy ayudaremos a Marta a organizar los talleres de la tarde en un centro ocupacional. Tenemos que conseguir que los talleres que comparten participantes se impartan en días diferentes utilizando el menor número de días posible.

🛠️ ¿Cómo funciona esta ficha interactiva?

Este entorno te guiará paso a paso por las cuatro etapas del proceso. El sistema irá validando tus respuestas para dejarte avanzar hasta los 10 puntos finales:

🎯 Etapa 1: Construcción del Grafo

• Instrucciones: Observa la tabla de Inscripciones. Si ves que una persona (por ejemplo, Juan) está apuntada a la vez en Informática (I) y en Yoga (Y), significa que esos dos talleres no se pueden dar el mismo día.

• Acción: Conecta los nodos en el lienzo. Toca el nodo I y luego el nodo Y para dibujar una línea entre ellos. Haz esto con todos los talleres que compartan al menos un participante. Si te equivocas, haz pulsación larga o clic derecho sobre la línea para borrarla. Al terminar, pulsa Verificar grafo.

📊 Etapa 2: Cálculo de Grados

• Instrucciones: El grado de un vértice es simplemente el número de líneas que salen de él (sus vecinos directos).

• Acción: Cuenta las aristas de cada nodo en el grafo que acabas de validar y rellena la tabla con los números correspondientes. Pulsa Verificar grados.

🎨 Etapa 3: Algoritmo de Coloreo (Estrategia Codiciosa)

• El sistema te obligará a seguir el orden matemático óptimo (Algoritmo de Welsh-Powell):

  1. Selecciona el nodo: Toca en el mapa el vértice que tenga el mayor grado de entre todos los que aún están en blanco.

  2. Elige color: Haz clic en uno de los colores de la paleta inferior para pintarlo.

  3. Nodos no adyacentes: El sistema te preguntará qué otros nodos independientes (que no estén conectados al que acabas de pintar) puedes colorear con ese mismo tono para aprovechar el día.

📅 Etapa 4: Conclusión y Distribución

• Acción: Responde cuántos días son necesarios en total (el número de colores que has usado). Luego, haz clic en Generar tabla y marca los talleres que van agrupados en cada uno de los días.

🏁 Finalización y entrega

Cuando completes la distribución, pulsa el botón flotante de la esquina inferior derecha: 📋 Ver calificación. Asegúrate de escribir tu nombre completo, comprueba tu nota y toma una captura de pantalla de la tarjeta final para subirla a Classroom como justificante de tu trabajo. ¡A por los 10 puntos!