46

Exercícios resolvidos: Algoritmos - Teoria e Prática - 3ª Ed. 2012

Thomas Cormen IBSN: 9788535236996

Elaborado por professores e especialistas

Passo 1 de 3keyboard_arrow_downkeyboard_arrow_up

Vamos provar aqui que árvores quaisquer são 2-coloridas, ou seja, seus nós podem ser pintados de somente 2 cores de forma que nós vinhos não tenham a mesma cor.

Passo 2 de 3keyboard_arrow_downkeyboard_arrow_up

Para isso, perceba que se percorrermos uma árvore a partir da raiz, alternando a cor de pintura de cada nó por que se passa, chegaremos a cada nó de somente uma forma, portanto o pintaremos de somente uma cor. Além disso é importante perceber que, como é uma árvore, a mesma é conexa e, portanto, nesse trajeto todos os nós serão visitados.

Passo 3 de 3keyboard_arrow_downkeyboard_arrow_up

Portanto, como uma árvore nunca tem ciclos e o que faz com que um grafo qualquer possa não ser 2-colorido é a possibilidade de o visitarmos duas vezes no trajeto tentando pintá-lo cada vez de uma cor, por causa da existência de ciclos de tamanhos ímpares, uma árvore sempre pode ser 2-colorida.

Navegar por capítulo

Aprenda agora com os exercícios mais difíceis

R$29,90/mês

Cancele quando quiser, sem multa

Aproveite também

  • check Todos os materiais compartilhados
  • check Biblioteca com mais de 5.000 livros
  • check Videoaulas exclusivas
  • check Resumos por tópicos