[obm-l] Re: [obm-l] Colorir grafo

[ghaeser@xxxxxxxxxxxxxx]

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
=========================================================================