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

["Domingos Jr." <dopikas@xxxxxxxxxx>]

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.


---- x ----

Legal, bem mais fácil que a minha!
Eu usava a hip. de indução completa, construia grafos de tamanho 1, 2, 2²,
..., 2^n, e + um vértice isolado, depois criava as regras de ligação (que
eram bem simples).
O interessante é que você usou o fato 2*2^n = 2^(n+1) enquanto eu fui pelo
caminho 1 + 2 + ... + 2^n = 2^(n+1) - 1.
Não implementei de fato o algoritmo, mas parece que as duas soluções são de
fato diferentes (as colorações resultantes são diferentes...), será que dá
pra conseguir mais que 2^n vértices com n cores?

[ ]'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
=========================================================================