Teoría de grafos - Colorear

La coloración de gráficos no es más que una forma sencilla de etiquetar componentes de gráficos como vértices, bordes y regiones bajo algunas restricciones. En un gráfico, no hay dos vértices adyacentes, bordes adyacentes o regiones adyacentes coloreadas con un número mínimo de colores. Este número se llamachromatic number y la gráfica se llama properly colored graph.

Mientras se colorea el gráfico, las restricciones que se establecen en el gráfico son los colores, el orden de coloración, la forma de asignar el color, etc. Se le da un color a un vértice o una región en particular. Así, los vértices o regiones que tienen los mismos colores forman conjuntos independientes.

Colorear Vertex

La coloración de vértices es una asignación de colores a los vértices de un gráfico 'G' de manera que no haya dos vértices adyacentes que tengan el mismo color. En pocas palabras, dos vértices de un borde no deben ser del mismo color.

Número cromático

El número mínimo de colores requeridos para colorear el vértice del gráfico 'G' se denomina número cromático de G, denotado por X (G).

χ (G) = 1 si y solo si 'G' es un gráfico nulo. Si 'G' no es un gráfico nulo, entonces χ (G) ≥ 2.

Example

Note - Se dice que una gráfica 'G' es n-cubrible si hay una coloración de vértice que usa como máximo n colores, es decir, X (G) ≤ n.

Región para colorear

El color de la región es una asignación de colores a las regiones de un gráfico plano de modo que no haya dos regiones adyacentes con el mismo color. Se dice que dos regiones son adyacentes si tienen un borde común.

Example

Eche un vistazo al siguiente gráfico. Las regiones 'aeb' y 'befc' son adyacentes, ya que hay un borde común 'be' entre esas dos regiones.

De manera similar, las otras regiones también se colorean según la adyacencia. Este gráfico está coloreado de la siguiente manera:

Example

El número cromático de Kn es

• n
• n–1
• [n/2]
• [n/2]

Considere este ejemplo con K ₄ .

En el gráfico completo, cada vértice es adyacente a los vértices restantes (n - 1). Por tanto, cada vértice requiere un nuevo color. De ahí el número cromático de K _n = n.

Aplicaciones de la coloración de gráficos

La coloración de gráficos es uno de los conceptos más importantes en la teoría de grafos. Se utiliza en muchas aplicaciones de la informática en tiempo real, como:

• Clustering
• Procesamiento de datos
• Captura de imagen
• Segmentación de imagen
• Networking
• Asignación de recursos
• Programación de procesos