Esta página contiene varios ejercicios corregidos sobre el modelado del Teoría de grafos y los problemas de colorante de gráfico. Consulte la página sobre teoría de grafos para obtener más información sobre los conceptos básicos de la teoría de grafos y varios problemas en la teoría de grafos.
Ejercicio 1
Considerando un conjunto de fichas de dominó utilizando los números 0, 1, 2, 3, 4, ya que cada ficha de dominó consta de dos dígitos distintos, como son el 1 y el 3, se plantea el siguiente problema: ¿es posible alinear todas las fichas 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 el gráfico.
Ejercicio 2
Piensa en la secuencia 01110100 como dispuesta en un patrón circular. Tenga en cuenta que cada uno de los ocho tripletes binarios posibles: 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 el momento. Las flechas que se alejan de un vértice se etiquetan con 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 dos últimos dígitos nuevos. Por ejemplo, el nodo 00 va al 01 con un arco llamado 1 y va al 00 con un arco llamado 0.
Para obtener todas las combinaciones posibles de tres dígitos, necesitamos recorrer el gráfico con un ciclo euleriano. Por el resultado del problema anterior, siempre hay dos flechas hacia afuera y dos flechas hacia cada vértice, y por el 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 cualquier caso, 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 vinculadas a un servidor, una subestación no puede enviar paquetes si algunas subestaciones ya están utilizando el enlace. La siguiente tabla muestra la capacidad de cada subestación para enviar un paquete en relación con las demás. Por ejemplo, un paquete de A no se puede enviar si ya hay un paquete de D, pero se puede enviar cuando B ha enviado un paquete.
Subestación | PARA | B | VS | D | mi | F | GRAMO |
no esta con | DE | D, E, F, G | P.EJ | A, B, E | A, B, C, D, F, G | B, E, G | B, C, E, F |
Representar los enlaces en un gráfico. ¿Cuántos paquetes debe manejar el servidor al mismo tiempo (valor máximo)?
El gráfico es cuatricromático.
Ejercicio 4
Una escuela debe pasar pruebas escritas a cuatro estudiantes: Pierre, Jean, Guillermo e Ibrahim. Siete disciplinas están involucradas: 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 el número mínimo de franjas horarias que se deben proporcionar para que ningún alumno tenga que realizar dos pruebas simultáneamente? ¿Cuál es el número cromático de un grafo completo? ¿Cómo enlazar números cromáticos en un gráfico?
Un vértice representa una disciplina, un borde conecta dos disciplinas si no pueden tener lugar al mismo tiempo. El problema se puede resolver buscando un número mínimo de colores. El subgrafo 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. Por experimento, el gráfico es tricromático.
ES 
FR 
EN