in

Coloración de gráficos | Conjunto 1 (Introducción y aplicaciones)

gfg 200x200 min

Coloración gráfica El problema es asignar colores a ciertos elementos de un gráfico sujeto a ciertas restricciones.

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 coloración de gráficos como Borde para colorear (Ningún vértice incide en dos aristas del mismo color) y Colorear Cara (Coloración de mapas geográficos) se puede transformar en coloración de vértices.

Número cromático: La menor cantidad de colores necesarios para colorear un gráfico G se denomina número cromático. Por ejemplo, los siguientes pueden tener un mínimo de 2 colores.

vertex_coloring

El problema para encontrar el número cromático de una gráfica dada 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) Hacer horario o tabla de tiempo: Supongamos que queremos hacer un horario de exámenes para una universidad. Tenemos una lista de diferentes asignaturas y alumnos matriculados en cada asignatura. Muchas asignaturas tendrían estudiantes comunes (del mismo lote, algunos estudiantes 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 una gráfica donde cada vértice es un tema y una arista entre dos vértices significa que hay un estudiante común. Así que este es un problema de coloración de gráficos en el que el número mínimo de intervalos de tiempo es igual al número cromático del gráfico.

2) Asignación de radiofrecuencia 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 un ejemplo de problema de coloración de gráficos en el que cada torre representa un vértice y un borde entre dos torres representa que están dentro del alcance de la otra.

3) Sudoku: Sudoku es también una variación del problema de coloración de gráficos en el que cada celda representa un vértice. Hay un borde entre dos vértices si están en la misma fila o 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 coloración de gráficos.

5) Gráficos bipartitos: Podemos comprobar si una gráfica es Bipartita o no coloreando la gráfica con dos colores. Si una gráfica dada es 2-coloreable, entonces es Bipartita, de lo contrario no. Vea esto para más detalles.

6) Colorear el mapa: 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 conferencia en video 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 existentes casi todas las semanas. La actualización no se puede implementar en todos los servidores al mismo tiempo, porque es posible que el servidor deba desactivarse para la instalación. Además, la actualización no debe realizarse de una en una, porque llevará mucho tiempo. Hay conjuntos de servidores que no se pueden desactivar juntos porque tienen ciertas funciones críticas. Ésta es una aplicación de programación típica del problema de coloración de gráficos. Resultó que 8 colores eran lo suficientemente buenos para colorear el gráfico de 75000 nodos. Para que pudieran instalar actualizaciones en 8 pasadas.

Pronto discutiremos diferentes formas de resolver el problema de coloración de gráficos.
https://youtu.be/_sdVx_dWnlk
Referencias:
Lec 6 | MIT 6.042J Matemáticas para la informática, otoño de 2010 | Conferencia en video

Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema discutido anteriormente.

¡Atención lector! No dejes de aprender ahora. Obtenga todos los conceptos importantes de DSA con el Curso autodidacta de DSA a un precio asequible para los estudiantes y prepárese para la industria. Para completar su preparación desde el aprendizaje de un idioma hasta DS Algo y muchos más, consulte Curso completo de preparación para entrevistas.

En caso de que desee asistir clases en vivo con expertos, consulte Clases en vivo de DSA para profesionales que trabajan y Programación competitiva en vivo para estudiantes.

Deja una respuesta

Tu dirección de correo electrónico no será publicada.

apple touch icon@2

java – ¿Convertir milisegundos a minutos y segundos?

Polvo para hornear vs bicarbonato de sodio: diferencia y comparación