Gabarito PG2

[Thierry Moreira]

Professor,

Acho que o sr. corrigiu errado uma questão minha. A questão pedia a alternativa falsa. A que eu marquei dizia:

"O algoritmo guloso de coloração sempre encontra uma coloração ótima para ciclos de tamanho par, independentemente da ordem em que os vértices são percorridos. "

Eu anexei o desenho de um C6, só para mostrar a rotulação dos vértices. Se o algoritmo guloso executar com a ordem (1, 4, 6, 5, 2, 3), ele colorirá o vértice 1 com a cor A, o vértice 4 com a cor A, o vértice 6 com a cor B, então o vértice 5 com a cor C. Utilizando 3 cores para isso. É um contra-exemplo.

Atenciosamente,

--
Thierry P. Moreira

[Joao Meidanis]

Ja' foi corrigido. Obrigado,

--Joao

On Fri, 29 Jun 2012, Thierry Moreira wrote:

> Professor,

> Acho que o sr. corrigiu errado uma quest�o minha. A quest�o pedia a

> alternativa falsa. A que eu marquei dizia:

> "O algoritmo guloso de colora��o sempre encontra uma colora��o �tima para
> ciclos de tamanho par, independentemente da ordem em que os v�rtices s�o
> percorridos.�"
>
> Eu anexei o desenho de um C6, s� para mostrar a rotula��o dos v�rtices. Se o
> algoritmo guloso executar com a ordem (1, 4, 6, 5, 2, 3), ele colorir� o
> v�rtice 1 com a cor A, o v�rtice 4 com a cor A, o v�rtice 6 com a cor B,
> ent�o o v�rtice 5 com a cor C. Utilizando 3 cores para isso. � um

> contra-exemplo.
>
> Atenciosamente,
>
>
> --
> Thierry P. Moreira
>
>

--
Joao Meidanis IC-UNICAMP
Institute of Computing Av. Albert Einstein, 1251
University of Campinas, Brazil 13083-852, Campinas, Sao Paulo
http://www.ic.unicamp.br/~meidanis Brazil