Please enable JavaScript.
Coggle requires JavaScript to display documents.
Coloração de Grafos (PROBLEMA DA MINIMIZAÇÃO (Encontrar um número mínimo…
Coloração de Grafos
PROBLEMA DA MINIMIZAÇÃO
-
k-coloração. Ex: 3-coloração -> C = {amarelo,verde,vermelho}
Uma classe de cores em uma coloração de um grafo G é um subconjunto de Vg contendo todos os vértices de uma única cor.
Uma coloração própria dos vértices de um grafo é uma coloração de vértices (pontos finais) de cada aresta sçao atribuídas cores diferentes.
o número cromático de um grafo G, é o menor número de cores diferentes necessárias para obter uma coloração própria de G.
COLORINDO VÉRTICES
Se o grafo tem n vértices, então seu número cromático é <=n
-
-
Um grafo com pelo menos uma aresta é 2-cromático, se e somente se não possui ciclos com comprimento ímpar.
PLANARIDADE
-
Um grafo é planar se seu esquema puder ser traçado em um plano de forma que duas arestas quaisquer se toquem, no máximo, em alguma extremidade.
Aplicação: Cartografia, Circuitos Digitais, Malhas de transportes terrestre, Construção de Viadutos, Malha de transporte aéreo.
Fórmula de Euler: n - m + f = 2, onde n = vértices, f = faces, m = arestas
ALGORITMO
-
-
Nenhum algoritmo de tempo polinomial pode obter a coloração mínima pois o problema de achar o número cromático de um grafo é NP-difícil.
Introdução
o estudo nasceu quando Francis Guthrie percebeu que era possível colorir o mapa da Inglaterra usando apenas 4 cores.
TEOREMA DAS 4 CORES
Dado um mapa plano, dividido em regiões, 4 cores são suficientes para colori-lo de forma que as regiões vizinhas não partilhem da mesma cor.
-
-
utilizando no máximo 4 cores, qualquer mapa pode ser colorido de forma que regiões adjacentes não tenham a mesma cor.
-
APLICAÇÃO
Coloração de mapas, definição de horário de provas, atribuições de frequências de rádio, separação de produtos explosivos, agendamento de cursos na universidade, alocação de registros para programação.
COLORAÇÃO DE ARESTAS
Índice cromático (diferente de número cromático) é o número mínimo de cores para colorir as arestas de G.
No tipo mais comum de coloração, as cores são atribuídas aos vértices.
Do ponto de vista matemático, o subconjunto de vértices com uma mesma cor é considerado uma partição de vértices. (subconjuntos independentes)
Podemos assumir que todos os grafos, para fins de coloração, são simples e conectados, já que arestas múltiplas e vértices isolados são irrelevantes para coloração de vértices
-