El problema de coloreado de gráficos consiste en asignar colores a ciertos elementos de un gráfico sujeto a ciertas restricciones.
La coloración de vértices es el problema de coloración de gráficos más común. El problema es, dados m colores, encontrar una forma de colorear los vértices de un gráfico de modo que no haya dos vértices adyacentes coloreados con el mismo color. Los otros problemas de coloreado de gráficos como Coloreado de bordes (Ningún vértice es incidente en dos bordes del mismo color) y Coloreado de caras (Coloreado de mapas geográficos) se pueden transformar en coloreado de vértices.
Número cromático: El número más pequeño de colores necesarios para colorear un gráfico G se llama su número cromático. Por ejemplo, lo siguiente se puede colorear con un mínimo de 2 colores.
El problema para encontrar el número cromático de un gráfico dado es NP Completo .
Aplicaciones de la coloración de gráficos:
El problema de la coloración de gráficos tiene un gran número de aplicaciones.
1) Elaboración de Calendario o Horario: Supongamos que queremos realizar un calendario de exámenes para una universidad. Tenemos una lista de diferentes materias y estudiantes matriculados en cada materia. Muchas asignaturas tendrían alumnos comunes (del mismo lote, algunos alumnos atrasados, etc). ¿Cómo programamos el examen para que no se programen dos exámenes con un estudiante común al mismo tiempo? ¿Cuántas franjas horarias mínimas se necesitan para programar todos los exámenes? Este problema se puede representar como un gráfico donde cada vértice es un sujeto y un borde entre dos vértices significa que hay un estudiante común. Entonces, este es un problema de coloreado de gráficos donde el número mínimo de intervalos de tiempo es igual al número cromático del gráfico.
2) Asignación de frecuencias de radio móvil : cuando se asignan frecuencias a torres, las frecuencias asignadas a todas las torres en la misma ubicación deben ser diferentes. ¿Cómo asignar frecuencias con esta restricción? ¿Cuál es el número mínimo de frecuencias necesarias? Este problema también es una instancia del problema de coloreado de gráficos en el que cada torre representa un vértice y un borde entre dos torres representa que están en el rango de la otra.
3) Sudoku: Sudoku también es una variación del problema de coloreado de gráficos en el que cada celda representa un vértice. Hay una arista entre dos vértices si están en la misma fila, en la misma columna o en el mismo bloque.
4) Asignación de registros : en la optimización del compilador, la asignación de registros es el proceso de asignar una gran cantidad de variables de programa de destino a una pequeña cantidad de registros de la CPU. Este problema también es un problema de coloreado de gráficos.
5) Gráficos bipartitos: podemos comprobar si un gráfico es bipartito o no coloreando el gráfico con dos colores. Si un gráfico dado es de 2 colores, entonces es bipartito, de lo contrario no. Vea esto para más detalles.
6) Coloreado de mapas: Mapas geográficos de países o estados donde no se puede asignar el mismo color a dos ciudades adyacentes. Cuatro colores son suficientes para colorear cualquier mapa (ver Teorema de los cuatro colores )
Puede haber muchas más aplicaciones: por ejemplo, la siguiente videoconferencia de referencia tiene un estudio de caso en 1:18.
Akamai ejecuta una red de miles de servidores y los servidores se utilizan para distribuir contenido en Internet. Instalan un nuevo software o actualizan los softwares existentes casi todas las semanas. La actualización no se puede implementar en todos los servidores al mismo tiempo, ya que es posible que se deba desactivar el servidor para la instalación. Además, la actualización no debe hacerse de una en una, porque llevará mucho tiempo. Hay conjuntos de servidores que no se pueden desarmar juntos porque tienen ciertas funciones críticas. Esta es una aplicación de programación típica del problema de coloreado de gráficos. Resultó que 8 colores eran lo suficientemente buenos para colorear el gráfico de 75000 Nodes. Así podrían instalar actualizaciones en 8 pasadas.
Pronto discutiremos diferentes formas de resolver el problema de coloreado de gráficos.
https://youtu.be/_sdVx_dWnlk
Referencias:
Lec 6 | MIT 6.042J Matemáticas para informática, otoño de 2010 | Video conferencia
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA