Mapas e Grafos
Vamos começar por rever alguns resultados relativos a “Coloração de Grafos”.
A coloração de um grafo simples é a atribuição de uma cor a cada vértice de um grafo, de
forma a que dois vértices adjacentes tenham cores diferentes.
O número cromático de um grafo é número mínimo de cores necessárias para a coloração
desse grafo.
1. Determina o número cromático dos seguintes grafos:
a.
b.
Netprof.pt
Mapa e Grafo Dual
A um mapa podemos associar um grafo planar, a que chamamos Grafo Dual, da seguinte forma:
• Cada região do mapa corresponde a um vértice no grafo
• Existe um arco entre dois vértices do grafo, se as regiões correspondentes do mapa
fizerem fronteira.
Exemplo:
Mapa
Grafo dual
2. Obtém o grafo dual do seguinte mapa:
Existe um teorema muito famoso – O teorema das quatro cores – que nos diz que o número
cromático de um grafo planar não é maior que 4.
Fazendo corresponder o mapa ao seu grafo dual, podemos concluir que o número de cores
necessárias para colorir um mapa, de modo a que regiões com a mesma fronteira não tenham a
mesma cor, é 4.
3. Recolhe diversos mapas e, a partir da coloração do grafo dual de cada mapa, procede à sua
coloração. Lembra-te que, no máximo, só precisas de 4 cores diferentes.
Netprof.pt