Esta página contiene varios ejercicios corregidos sobre modelado de teoría de grafos y problemas de coloración. Consulte la página de teoría de grafos para conocer los conceptos básicos de la teoría de grafos y varios problemas de la teoría de grafos.
Ejercicio 1
Considerando un juego de dominó utilizando los números 0, 1, 2, 3, 4, ya que en cada dominó se incluyen dos dígitos distintos, como 1 y 3, se propone el siguiente problema: ¿Es posible alinear todas las fichas de dominó de modo que cuando dos peones "tocan" los números "en contacto" son idénticos?
Muestre el problema como un gráfico completo K5. El problema es encontrar un ciclo euleriano en la gráfica.
Ejercicio 2
Considere que la secuencia 01110100 está organizada en un patrón circular. Observe que cada uno de los ocho posibles triples binarios: 000, 001, 011 ,. . . , 111 aparecen exactamente una vez en la lista circular. ¿Puedes construir una lista similar de longitud 16 donde los cuatro patrones de dígitos binarios aparezcan exactamente una vez cada uno?
Es un gráfico con cuatro vértices, cada uno etiquetado con uno de los posibles pares de dígitos binarios. Imagina que cada nodo son los dos últimos dígitos del patrón hasta ahora. Las flechas que se alejan de un vértice están etiquetadas como 0 o 1: los dos valores posibles para el siguiente dígito que se pueden agregar al patrón, y los extremos de las flechas indican los nuevos dos dígitos finales. Por ejemplo, el nodo 00 va a 01 con un arco llamado 1 y va a 00 con un arco llamado 0.
Para lograr todas las combinaciones posibles de tres dígitos, necesitamos recorrer la gráfica con un ciclo euleriano. Debido al resultado del problema anterior, siempre hay dos flechas hacia afuera y dos flechas hacia cada vértice, y debido al resultado del problema anterior, debe haber un circuito euleriano.
La situación es la misma para cualquier número de dígitos, excepto que el gráfico se volverá cada vez más complejo. Para la versión de 4 dígitos, habrá 8 vértices y 16 aristas, y así sucesivamente. Pero en todos los casos, habrá dos aristas entrando y dos saliendo de cada vértice, por lo que es posible un circuito euleriano.
Ejercicio 3
Un servidor puede enrutar un máximo de paquetes al mismo tiempo. Siete subestaciones están conectadas a un servidor, una subestación no puede enviar paquetes si algunas subestaciones ya utilizan el enlace. La siguiente tabla presenta cada subestación de la capacidad de enviar un paquete en función de las demás. Por ejemplo, un paquete de A no se puede enviar si ya existe un paquete de D, pero se puede enviar cuando B envió un paquete.
Subestación | PARA | B | VS | D | mi | F | GRAMO |
No esta permitido con | DE | D, E, F, G | P.EJ | A, B, E | A, B, C, D, F, G | B, E, G | B, C, E, F |
Representa los enlaces en un gráfico. ¿Cuántos paquetes tiene que gestionar el servidor al mismo tiempo (valor máximo)?
El gráfico es 4 cromático.
Ejercicio 4
Una escuela debe aprobar pruebas escritas a cuatro estudiantes: Pierre, Jean, Guillermo e Ibrahim. Están involucradas siete disciplinas: matemáticas, física, biología, francés, inglés, español e historia.
Pierre debe aprobar matemáticas, física e inglés, Jean matemáticas, biología y francés, Guillermo matemáticas, inglés y español e Ibrahim física, francés e historia.
¿Cuál es la cantidad mínima de franjas horarias que se puede esperar para que ningún estudiante tenga que aprobar dos pruebas simultáneamente? ¿Cuál es el número cromático de una gráfica completa? ¿Cómo unir números cromáticos en un gráfico?
Un vértice representa una disciplina, un borde une dos disciplinas si no pueden tener lugar al mismo tiempo. El problema se puede solucionar buscando un número mínimo de colores. El subgráfico completo más grande es K3, por lo que hay al menos 3 colores. El grado máximo es cinco, por lo que hay como máximo 5 colores. Experimentando, el gráfico es tricromático.
ES 
FR 
EN