Vera Clotilde Carneiro
UFRGS

Este artigo foi motivado pela seguinte questão, proposta na prova de vestibular para a  Escola Agrotécnica Federal Presidente Juscelino Kubitschek de Bento Gonçalves, Rio Grande do Sul.

Ao colorir um mapa, pode-se usar uma mesma cor mais de uma vez, desde que dois países vizinhos tenham cores diferentes.

De quantas maneiras diferentes pode-se colorir o mapa ao lado, usando apenas 4 cores?

Esse problema requer apenas um pouco de raciocínio. Com 4 cores pode-se pintar o mapa da figura de 48 maneiras diferentes. No entanto, a maioria dos estudantes calcula que só há 24 maneiras, ou seja, 4!, permutação de n = 4 elementos. O que se observa é a tendência que nossos alunos trazem do segundo grau de apelar, em primeiro lugar, para fórmulas memorizadas e, em último, para o simples e saudável hábito de pensar.

Esse trabalho apresenta resultados referentes à coloração de mapas e, indo um pouco além desse tema, propõe que a Combinatória seja desenvolvida de forma a incentivar o desenvolvimento do pensamento e do raciocínio independente.

O problema da coloração de mapas é antigo e serviu de impulso para o desenvolvimento da teoria dos grafos. (Leia sobre grafos em [1] e [2].)

Todo mapa pode ser identificado com um grafo, onde os países são os vértices e uma fronteira entre dois países é representada por uma aresta ligando dois vértices. O mapa da página anterior pode ser representado pelo grafo ao lado.

Número cromático de um mapa, ou de um grafo, é o menor número de cores necessário para pintá-lo, respeitando sempre a idéia que dois países vizinhos no mapa, ou dois pontos interligados no grafo, não podem ter a mesma cor. Vamos representar esse número por NCROM.

Em 1852 foi formulada a conjetura que deu origem ao teorema das quatro cores, demonstrado em 1977, com auxílio de computadores. Esse teorema afirma que com 4 cores é possível pintar qualquer mapa. Equivalentemente, qualquer grafo que tenha desenho plano sem arestas que se intersectem pode ser colorido com   4   cores.

Por exemplo, veja os seguintes grafos tipo polígono:

3 vértices                              4 vértices                                5 vértices
NCROM = 3 cores             NCROM = 2 cores             NCROM = 3 cores
 

Mais geralmente, se o grafo "polígono" tem n vértices, o NCROM é 2 se   n   for par, e é 3 se  n   for ímpar.

Analisando o grafo correspondente ao nosso mapa, vemos que 2 cores não bastam para colori-lo, pois temos um subgrafo "triângulo". Nesse caso o NCROM é   3.

Usando x cores, com x maior ou igual ao NCROM, existem diferentes maneiras de colorir o mesmo grafo. Esse número de colorações pode ser obtido através dos valores p(x) de um polinômio associado ao gráfico, cujo grau  n  corresponde ao número de vértices. Tal polinômio é chamado polinômio cromático, e veremos como construí-lo no nosso problema. (Veja mais detalhes sobre coloração em [3], [4] e [5].)

Muitos problemas de Combinatória podem ser resolvidos com uma conjugação dos dois processos abaixo e alguma habilidade.

(a)  Processo de multiplicação

A resolução do problema proposto da coloração de mapas é um exemplo típico do uso desse processo. Esse processo pode ser identificado ao verbalizar a solução.

    Pode-se escolher qualquer uma das 4 cores para o Brasil,

    para cada uma dessas, podem-se escolher 3 cores para o Paraguai,

    para cada uma dessas, podem-se escolher 2 cores para a Argentina,

   para cada uma dessas, podem-se escolher 2 cores para o Uruguai, pois esse país não tem fronteira com o Paraguai.

Daí a solução: 4 x 3 x 2 x 2 = 48  maneiras diferentes de colorir o mapa.

No mapa que estamos considerando, o polinômio cromático para x > 3  cores é:

p(x,4) = x(x l)(x 2)²

Refaça o raciocínio anterior, colocando x em lugar de 4 e você poderá ver como o polinômio cromático é construído.

(b)  Processo de adição

Esse é o processo natural de divisão de um problema em diferentes casos, quando aparecem dúvidas do tipo "pode ser assim ou assim . . ."

No mesmo problema anterior, chegaríamos a um impasse se mudássemos a ordem na coloração.

    Começando no Paraguai, temos à disposição 4 cores.

    Para a Argentina sobram 3 cores.

    Para o Uruguai temos 3 cores porque podemos repetir a cor do Paraguai.

   E, finalmente, para o Brasil? Pode ser só 1 se as outras forem todas diferentes ou pode ser 2 se as cores do Paraguai e Uruguai forem iguais.

OPA!   Temos que dividir em casos.

Ou Paraguai e Uruguai têm cores diferentes ou têm a mesma cor.

   Caso 1 (cores diferentes):
4(Parag.)  x  3(Arg.)  x  2(Urug.)  x  l (Brasil) = 24.

 Caso 2 (cores iguais no Paraguai e Uruguai): 4 x 3 x 1 x 2 = 24.

A resposta final é a soma das respostas para rada possibilidade: 48,   como já sabíamos. (Veja mais sobre esses processos em [3].)

Observe que, se tivéssemos x > 3 cores, o polinômio cromático obtido com essa divisão em dois casos seria:

Cores diferentes     +     Cores iguais

x(x 1)(x 2)(x 3) + x(x l)(x 2) = x(x l)(x 2)².

Reduzindo o problema à análise de grafos, estamos dividindo o grafo original em dois outros diferentes. O primeiro corresponde a um grafo completo de 4 vértices, e o segundo, a um grafo de 3 vértices, como se o Uruguai (ou o Paraguai) fosse eliminado da questão:

A Combinatória é um dos conteúdos da Matemática Discreta, área da Matemática que estuda os conceitos e situações que dependem dos números inteiros (ou outros conjuntos discretos). As seqüências e somatórios, grafos e matrizes, combinatória e probabilidades são conteúdos interrelacionados na Matemática Discreta e deveriam estar presentes mantendo suas relações nos currículos do 2.° grau.

Problemas de Combinatória podem ser resolvidos com os processos de multiplicação, adição (e divisão). As definições e fórmulas de arranjo, permutação e combinação podem ser apresentadas e deduzidas entre as questões propostas e até podem ser usadas para resolver outras questões mais rapidamente; no entanto, a memorização dessas fórmulas, além de em nenhum momento conseguir substituir o raciocínio, prejudica a aprendizagem quando, de tão destacadas, deixam de ser parte e são confundidas com o todo.

A coloração de mapas é apenas um entre muitos problemas que podem ser explorados nessa área. A visita aos grafos merece ser feita na era dos computadores, das redes de comunicação e de transportes e dos intrincados processos decisórios. Existem diversas aplicações simples, porém muito interessantes, envolvendo grafos.

Para a maioria dos problemas da Combinatória não há algoritmos preestabelecidos. Cabe ao professor criar oportunidades para que seus alunos possam analisar, discutir em grupos, escrever, expor e, finalmente, resolver de diferentes maneiras muitas e variadas questões, comparando-as e identificando semelhanças e diferenças, até criar a sua forma própria de pensar.

Referências Bibliográficas

[1]    LIMA, E.L. Alguns problemas clássicos sobre grafos. RPM 12, 1988, 36 42.

[2]    PITOMBEIRA, J.B. O problema, das ligações de água., luz e telefone: uma. aplicação da fórmula, de Euler. RPM 11, 1987, 9-16.

[3]    MORGADO et al. Análise Combinatória e Probabilidades. Rio de Janeiro, SBM, 1991, 1516, 27 28.

[4]    RABUSKE, M. Introdução à teoria dos grafos.   Florianópolis, Editora da UFSC, 1992, 144-146, 156-163.

[5]     Santos, P. et ai.   Introdução à Análise Combinatória.  Campinas, Editora da UNICAMP, 1995, 246-248.