Resolvido: Algoritmos - Teoria e Prática - 3ª Ed. 2012 | Cap 22 Ex 1PA
51
Algoritmos - Teoria e Prática - 3ª Ed. 2012

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

Thomas Cormen IBSN: 9788535236996

Elaborado por professores e especialistas

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.

Navegar por capítulo

Aprenda agora com os exercícios mais difíceis

R$29,90/mês

Assine o PremiumCancele quando quiser, sem multa

Aproveite também

  • check Todos os materiais compartilhados
  • check Biblioteca com 5.000 livros, escolha 5 por mês
  • check Videoaulas exclusivas
  • check Resumos por tópicos