Da pra melhorar isto,acho.Veja o artigo do Gugu e veja que da pra dispensar algumas cores.E esta construçao tem num livro do Tim
ghaeser@zipmail.com.br wrote:
base: n=1, n=2 .. trivial.
hip: consigo pintar as arestas de um grafo completo de 2^n vertices utilizando
n cores tal que nao exista triangulo monocromatico.
passo: podemos construir o grafo completo de 2^(n+1) vertices, fazendo uma
cópia exata do grafo de 2^n vertices (repetindo inclusive a coloração ..
que por hipotese existe) .. para o grafo ser completo cada vértice do grafo
de 2^n vertices deve estar ligado com cada vértice da cópia exata .. basta
pintar estas arestas de ligação com a (n+1)-ésima cor .. e garantimos que
nao existe triangulo monocromatico.
-- Mensagem original --
>Um probleminha pra vocês:
>
>Construa um grafo G = (V, E) completo (todos par de vértices é conectado
>por
>uma aresta) de 2^n vértices e pinte as arestas deste usando n cores de
forma
>que não exista um triângulo
monocromático (ie: u, v, w pert. V, cor(u,
v)
>=
>cor(v, w) = cor(u, w)).
>
>Depois eu posto a minha solução!
>
>[ ]'s
>
>=========================================================================
>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
>=========================================================================
>
------------------------------------------
Use o melhor sistema de busca da Internet
Radar UOL - http://www.radaruol.com.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
=========================================================================