31

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

Thomas CormenIBSN: 9788535236996

Elaborado por professores e especialistas

ALUNOS QUE TAMBÉM VISUALIZARAM

  • +6.755

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

Depoimentos de estudantes que já assinaram o Exercícios Resolvidos

Nathalia Nascimento fez um comentárioCEFET/RJ • Engenharia
Foi um apoio àquelas aulas que não acabam totalmente com as dúvidas ou mesmo naquele momento de aprender o conteúdo sozinha. Além disso, dispensou a necessidade de um orientador e por isso, permitiu que eu estudasse em qualquer local e hora.
Valdivam Cardozo fez um comentárioUFRB • Engenharia
Tive uma sensação maior de autonomia nos estudos, as vezes era frustante não conseguir resolver uma determinada questão e nem sempre os professores corrigem as listas que passam.