Coloracao de Grafos

Coloração de grafos

Trabalho interdisciplinar de
Matemática Computacional e
Teoria Grafos para Computação sobre Coloração de grafos

Sumário

- Introdução ............................................................................... 4
- Formulação ............................................................................. 4
- Histórico .................................................................................. 4
- Aplicações ............................................................................... 5
- Algoritmos e Soluções ............................................................ 7
- Implementação, Experimentos e Resultados........................ 9
- Conclusão ................................................................................ 14
- Referência ............................................................................... 14

3

Introdução
O problema de coloração de vértices em grafos é um dos problemas mais estudados em
Teoria dos Grafos devido à sua relevância em campos práticos e teóricos. Esse problema pode ser definido como o problema de achar o menor número de cores, k, tal que exista uma (k)- coloração do grafo G, ou seja, a atribuição de k cores a cada um dos vértices de G, sem que vértices adjacentes recebam a mesma cor. Este número mínimo de cores, k, é denominado número cromático de G.
Este trabalho procura introduzir a teoria da coloração de grafos, formulação,histórico e aplicações. Formulação
O objetivo deste trabalho é otimizar a coloração para o mínimo de cores possíveis
Minimizar Z= Utilizar o menor número de cores possíveis
Sujeito a: As cores dos vértices adjacentes sejam distintas

Histórico
Os primeiros resultados sobre coloração de grafos lidam quase que exclusivamente com grafos planares na forma da coloração de mapas. Enquanto tentava colorir um mapa dos condados da Inglaterra, Francis Guthrie postulou a conjectura das quatro cores, notando que quatro cores eram