[obm-l] PROBLEMAS CROMÁTICOS!

[jorgeluis@xxxxxxxxxxxxx]

Olá, Pessoal!

Pelo menos quatro cores são necessárias para se resolver o problema geral de
colorir um mapa. Como ninguém conseguiu produzir um mapa que necessitasse de
mais de quatro cores, foi formulada uma conjectura de que quatro cores são, de
fato, suficientes. Essa conjectura ficou conhecida como o problema das quatro
cores. Ele foi proposto, pela primeira vez, ao matemático Augustus De Morgan
por um de seus alunos em 1852 e recebeu, mais tarde, bastante atenção.
Permaneceu sem demonstração, no entanto, por mais de 100 anos. Em 1976, dois
matemáticos da Universidade de Illinois, Wolfgang Haken e Kenneth Appel, usaram
um computador para analisar um grande número de casos em uma demonstração por
absurdo, verificando, assim, a conjectura das quatro cores.

O problema das cinco cores diz que o número cromático de um grafo planar simples
e convexo é, no máximo, 5. Enquanto o teorema das quatro cores é muito difícil
de provar, o teorema das cinco cores pode ser provado por indução no número de
nós do grafo.

O problema das seis cores pode ser provado como um problema de colorir um mapa
sem usar o grafo dual.

A propósito, prove que, em qualquer árvore com n nós, o número total de
extremidades de arcos é 2n - 2.

Abraços!

______________________________________________
WebMail UNIFOR - http://www.unifor.br.
=========================================================================
Instruções para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html
=========================================================================