Teoria de grafos - Coloração

A coloração do gráfico nada mais é do que uma maneira simples de rotular os componentes do gráfico, como vértices, arestas e regiões, sob algumas restrições. Em um gráfico, dois vértices adjacentes, arestas adjacentes ou regiões adjacentes não são coloridas com um número mínimo de cores. Este número é chamado dechromatic number e o gráfico é chamado de properly colored graph.

Durante a coloração do gráfico, as restrições que são definidas no gráfico são as cores, a ordem de coloração, a forma de atribuir cor, etc. Uma coloração é dada a um vértice ou região particular. Assim, os vértices ou regiões com as mesmas cores formam conjuntos independentes.

Coloração de vértices

A coloração de vértices é uma atribuição de cores aos vértices de um gráfico 'G', de forma que dois vértices adjacentes não tenham a mesma cor. Simplificando, dois vértices de uma aresta não devem ser da mesma cor.

Número Cromático

O número mínimo de cores necessário para a coloração do vértice do gráfico 'G' é chamado de número cromático de G, denotado por X (G).

χ (G) = 1 se e somente se 'G' for um gráfico nulo. Se 'G' não for um gráfico nulo, então χ (G) ≥ 2.

Example

Note - Diz-se que um gráfico 'G' é n-cobrível se houver uma coloração de vértices que usa no máximo n cores, ou seja, X (G) ≤ n.

Coloração da região

A coloração da região é uma atribuição de cores às regiões de um gráfico planar de forma que duas regiões adjacentes não tenham a mesma cor. Diz-se que duas regiões são adjacentes se tiverem uma aresta comum.

Example

Dê uma olhada no gráfico a seguir. As regiões 'aeb' e 'befc' são adjacentes, pois há uma borda comum 'be' entre essas duas regiões.

Da mesma forma, as outras regiões também são coloridas com base na adjacência. Este gráfico é colorido da seguinte forma -

Example

O número cromático de Kn é

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

Considere este exemplo com K 4 .

No gráfico completo, cada vértice é adjacente aos vértices restantes (n - 1). Portanto, cada vértice requer uma nova cor. Daí o número cromático de K n = n.

Aplicações de Coloração de Gráficos

A coloração de grafos é um dos conceitos mais importantes na teoria dos grafos. É usado em muitas aplicações em tempo real da ciência da computação, como -

  • Clustering
  • Mineração de dados
  • Captura de imagem
  • Segmentação de imagem
  • Networking
  • Alocação de recursos
  • Agendamento de processos