24

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.283

Passo 1 de 4keyboard_arrow_downkeyboard_arrow_up

Devemos provar as propriedades de uma busca em largura de um grafo não dirigido. Primeiramente, temos a propriedade de que não há nenhuma aresta de retorno e nenhuma aresta direta. Consideremos uma aresta como uma aresta de retorno ou aresta direta. Como todas as arestas de são exploradas na busca antes de explorarmos qualquer uma de suas arestas descendentes, a aresta é explorada no momento que e explorada. Assim, concluímos que a propriedade é válida.

Passo 2 de 4keyboard_arrow_downkeyboard_arrow_up

A segunda propriedade diz que para cada aresta de árvore temos . Em uma busca em largura, uma aresta é aresta de árvore quando é definido. Isso ocorre somente quando . Após a definição dos valores, e não são alterados posteriormente. Assim, a propriedade é válida.

Passo 3 de 4keyboard_arrow_downkeyboard_arrow_up

A terceira propriedade diz que para cada aresta cruzada temos ou . Uma aresta é cruzada quando é visitado antes de . Como é visitado primeiro, o vértice já deve estar na fila nesse moimento. Caso contrário, a aresta é uma aresta de árvore. Como, está na fila, ou . Assim, a propriedade é válida.

Passo 4 de 4keyboard_arrow_downkeyboard_arrow_up

Portanto, provamos que todas as propriedades dadas são válidas.

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.