Coloración de gráficos
La coloración de gráficos se puede describir como un proceso de asignación de colores a los vértices de un gráfico. En esto, no se debe utilizar el mismo color para rellenar los dos vértices adyacentes. También podemos llamar coloración de gráficos como coloración de vértices. Al colorear gráficos, debemos tener cuidado de que un gráfico no contenga ninguna arista cuyos vértices finales estén coloreados del mismo color. Este tipo de gráfico se conoce como gráfico coloreado correctamente.
Ejemplo de coloración de gráficos
creación de tabla de oráculo
En este gráfico, mostramos el gráfico coloreado correctamente, que se describe a continuación:
El gráfico anterior contiene algunos puntos, que se describen a continuación:
- No se puede utilizar el mismo color para colorear los dos vértices adyacentes.
- Por lo tanto, podemos llamarlo un gráfico coloreado correctamente.
Aplicaciones de la coloración de gráficos.
Existen varias aplicaciones de coloración de gráficos. Algunas de sus aplicaciones importantes se describen a continuación:
- Asignación
- colorear mapa
- Programar las tareas
- Sudokus
- preparar el horario
- La resolución de conflictos
Número cromático
El número cromático se puede describir como el número mínimo de colores necesarios para colorear correctamente cualquier gráfico. En otras palabras, el número cromático se puede describir como un número mínimo de colores que se necesitan para colorear cualquier gráfico de tal manera que a dos vértices adyacentes de un gráfico no se les asigne el mismo color.
Ejemplo de número cromático:
Para comprender el número cromático, consideraremos una gráfica, que se describe a continuación:
El gráfico anterior contiene algunos puntos, que se describen a continuación:
- No se utiliza el mismo color para colorear los dos vértices adyacentes.
- El número mínimo de colores de este gráfico es 3, el cual es necesario para colorear adecuadamente los vértices.
- Por tanto, en este gráfico, el número cromático = 3
- Si queremos colorear correctamente este gráfico, en este caso se requieren al menos 3 colores.
Tipos de número cromático de gráficos:
Existen varios tipos de número cromático de gráficas, que se describen a continuación:
Gráfico de ciclo:
Un gráfico se conocerá como gráfico de ciclo si contiene 'n' aristas y 'n' vértices (n >= 3), que forman un ciclo de longitud 'n'. Solo puede haber 2 o 3 grados de todos los vértices en el gráfico de ciclo.
Número cromático:
- El número cromático en un gráfico de ciclo será 2 si el número de vértices en ese gráfico es par.
- El número cromático en un gráfico de ciclo será 3 si el número de vértices en ese gráfico es impar.
Ejemplos de gráfico de ciclo:
Hay varios ejemplos de gráficos de ciclos. Algunos de ellos se describen a continuación:
Ejemplo 1: En el siguiente gráfico tenemos que determinar el número cromático.
Solución: En el gráfico de ciclo anterior, hay 3 colores diferentes para tres vértices y ninguno de los vértices adyacentes está coloreado con el mismo color. En este gráfico, el número de vértices es impar. Entonces
Número cromático = 3
Ejemplo 2: En el siguiente gráfico tenemos que determinar el número cromático.
Solución: En el gráfico de ciclo anterior, hay 2 colores para cuatro vértices y ninguno de los vértices adyacentes está coloreado con el mismo color. En este gráfico, el número de vértices es par. Entonces
Número cromático = 2
Ejemplo 3: En el siguiente gráfico tenemos que determinar el número cromático.
Solución: En el gráfico anterior, hay 4 colores diferentes para cinco vértices y dos vértices adyacentes están coloreados con el mismo color (azul). Entonces este gráfico no es un gráfico cíclico y no contiene un número cromático.
Ejemplo 4: En el siguiente gráfico tenemos que determinar el número cromático.
Solución: En el gráfico anterior, hay 2 colores diferentes para seis vértices y ninguno de los vértices adyacentes está coloreado con el mismo color. En este gráfico, el número de vértices es par. Entonces
Número cromático = 2
Gráfico del planificador
Un gráfico se conocerá como gráfico planificador si se dibuja en un plano. Los bordes del gráfico del planificador no deben cruzarse.
Número cromático:
- En un gráfico planificador, el Número cromático debe ser Menor o igual a 4.
- El gráfico del planificador también se puede mostrar en todos los gráficos de ciclo anteriores excepto en el ejemplo 3.
Ejemplos de gráfico plano:
Hay varios ejemplos de gráficos más planos. Algunos de ellos se describen a continuación:
Ejemplo 1: En el siguiente gráfico tenemos que determinar el número cromático.
Solución: En el gráfico anterior, hay 3 colores diferentes para tres vértices y ninguno de los bordes de este gráfico se cruza. Entonces
lista de estados
Número cromático = 3
Aquí, el número cromático es menor que 4, por lo que esta gráfica es una gráfica plana.
Ejemplo 2: En el siguiente gráfico tenemos que determinar el número cromático.
Solución: En el gráfico anterior, hay 2 colores diferentes para cuatro vértices y ninguno de los bordes de este gráfico se cruza. Entonces
Número cromático = 2
Aquí, el número cromático es menor que 4, por lo que esta gráfica es una gráfica plana.
Ejemplo 3: En el siguiente gráfico tenemos que determinar el número cromático.
Solución: En el gráfico anterior, hay 5 colores diferentes para cinco vértices y ninguno de los bordes de este gráfico se cruza. Entonces
Número cromático = 5
Aquí, el número cromático es mayor que 4, por lo que esta gráfica no es una gráfica plana.
Ejemplo 4: En el siguiente gráfico tenemos que determinar el número cromático.
Solución: En el gráfico anterior, hay 2 colores diferentes para seis vértices y ninguno de los bordes de este gráfico se cruza. Entonces
Número cromático = 2
Aquí, el número cromático es menor que 4, por lo que esta gráfica es una gráfica plana.
Gráfico completo
Un gráfico se considerará completo si solo se utiliza una arista para unir cada dos vértices distintos. Cada vértice de un gráfico completo está conectado con todos los demás vértices. En este gráfico, cada vértice estará coloreado con un color diferente. Eso significa que en el gráfico completo, dos vértices no contienen el mismo color.
Número cromático
En un gráfico completo, el número cromático será igual al número de vértices de ese gráfico.
Ejemplos de gráfico completo:
operadores javascript
Hay varios ejemplos de gráficos completos. Algunos de ellos se describen a continuación:
Ejemplo 1: En el siguiente gráfico tenemos que determinar el número cromático.
Solución: Hay 4 colores diferentes para 4 vértices diferentes y ninguno de los colores es igual en el gráfico anterior. Según la definición, un número cromático es el número de vértices. Entonces,
Número cromático = 4
Ejemplo 2: En el siguiente gráfico tenemos que determinar el número cromático.
Solución: Hay 5 colores diferentes para 5 vértices diferentes y ninguno de los colores es igual en el gráfico anterior. Según la definición, un número cromático es el número de vértices. Entonces,
Número cromático = 5
Ejemplo 3: En el siguiente gráfico tenemos que determinar el número cromático.
Solución: Hay 3 colores diferentes para 4 vértices diferentes y un color se repite en dos vértices en el gráfico anterior. Entonces este gráfico no es un gráfico completo y no contiene un número cromático.
Gráfica bipartita
Un gráfico se conocerá como gráfico bipartito si contiene dos conjuntos de vértices, A y B. El vértice de A solo puede unirse con los vértices de B. Eso significa que las aristas no pueden unir los vértices con un conjunto.
Número cromático
En cualquier gráfico bipartito, el número cromático siempre es igual a 2.
Ejemplos de gráfico bipartito:
Hay varios ejemplos de gráficos bipartitos. Algunos de ellos se describen a continuación:
Ejemplo 1: En el siguiente gráfico tenemos que determinar el número cromático.
Solución: Hay 2 conjuntos diferentes de vértices en el gráfico anterior. Entonces el número cromático de todos los gráficos bipartitos siempre será 2. Entonces
Número cromático = 2
Árbol:
Un gráfico conexo se conocerá como árbol si no hay circuitos en ese gráfico. En un árbol, el número cromático será igual a 2 sin importar cuántos vértices haya en el árbol. Todo grafo bipartito es también un árbol.
Número cromático
En cualquier árbol, el número cromático es igual a 2.
imagen de rebajas
Ejemplos de árbol:
Hay varios ejemplos de árbol. Algunos de ellos se describen a continuación:
Ejemplo 1: En el siguiente árbol tenemos que determinar el número cromático.
Solución: Hay 2 colores diferentes para cuatro vértices. Un árbol con cualquier número de vértices debe contener el número cromático 2 en el árbol de arriba. Entonces,
Número cromático = 2
Ejemplo 2: En el siguiente árbol tenemos que determinar el número cromático.
Solución: Hay 2 colores diferentes para cinco vértices. Un árbol con cualquier número de vértices debe contener el número cromático 2 en el árbol de arriba. Entonces,
Número cromático = 2
Ejemplo de la vida real de número cromático
Supongamos que Marry es gerente de la empresa Xyz. La empresa contrata algunos empleados nuevos y tiene que crear un programa de capacitación para esos nuevos empleados. Tiene que programar las tres reuniones y está tratando de utilizar los pocos espacios de tiempo tanto como sea posible para las reuniones. Si hay un empleado que tiene que estar en dos reuniones diferentes, entonces el gerente debe utilizar horarios diferentes para esas reuniones. Supongamos que queremos obtener una representación visual de esta reunión.
Para la representación visual, Marry usa el punto para indicar la reunión. Si hay un empleado que tiene dos reuniones y necesita unirse a ambas, entonces ambas reuniones se conectarán con la ayuda de un borde. Las diferentes franjas horarias se representan con ayuda de colores. Entonces el administrador llena los puntos con estos colores de tal manera que dos puntos no contengan el mismo color que comparte un borde. (Eso significa que un empleado que necesita asistir a las dos reuniones no debe tener el mismo horario). La representación visual de esto se describe a continuación:
