Grafo

Teoria
Grafos
dos

1

Teoria dos Grafos
• Para um conjunto de objetos, observamos:
1. O conteúdo dos objetos, e
2. a estrutura do conjunto, ou seja , as relações entre os objetos.
A Teoria dos Grafos (TG) permite que se concentre no segundo ponto, fazendo abstração do primeiro.
2

Teoria dos Grafos
• Diagramas representam situações reais
– nós (vértices): representam objetos
– enlaces (arestas): relações entre objetos
Ex.: Seja o Grafo G – Quem conhece Paulo?
Pedro
Joana conhece João

Paulo conhece Antonia conhece Maria
3

Teoria dos Grafos
• 1847 - Kirchhof
– Estudo de circuitos elétricos (não eram CI´s!) utilizando grafos
• 1857 - Cayley
– Enumeração de isômeros dos hidrocarbonatos alifáticos saturados, em química orgânica
• 1869 - Jordan
Estudo de Árvores (estritamente matemático)
4

Teoria dos Grafos
• 1879 - Kempe
Apresenta a Conjectura das 4 cores apresentada por
Guthrie a De Morgan
(Provar que todo mapa geográfico desenhado no plano e dividido em um número qualquer de regiões pode ser colorido utilizando-se 4 cores, não é necessário mais que isso, sem que duas regiões fronteiriças recebam a mesma cor. Prox. slide)
– Foi provado que 5 cores podiam ser usadas(mas todos já sabiam que 4 era possível)
– Quase 100 anos se passaram até que a solução para as 4 cores foi provada.
•1977 - Appel e Haken: Provam matematicamente
5

Teoria dos Grafos
• Abrindo um parênteses: Com 4 cores ...

6

Teoria dos Grafos
• Com 3 cores!

7

Teoria dos Grafos
•Tente este com 3 cores:

8

Teoria dos Grafos
Conclusão:
“Todo grafo planar pode ser colorido com 4 cores (não mais que isso) sem que hajam regiões adjacentes com cores iguais”
É obvio que pode-se colorir alguns grafos com 3 cores, 2 cores (ou 1!).
Mas estes mapas não possuem características de mapas geográficos.
9