sexta-feira, 17 de maio de 2013

MO417 - Questão para a prova oral

Número: 2013-070

Enunciado: Considere uma busca em profundidade no grafo abaixo.

 
Definimos d[u] como o carimbo de tempo registrado quando u é descoberto e f[u] como o carimbo de tempo registrado quando a busca termina de examinar a lista de adjacências de u. Visto que a busca pode iniciar-se a partir de qualquer vértice, e continuar em componentes ainda não atingidas reiniciando-se também em qualquer vértice não ainda descoberto, é possível afirmar que:
  1. Se d[A] > d[E] então f[A] < f[E]
  2. Se d[A] < d[B] então f[C] > f[E]
  3. Se f[F] < f[B] então d[B] < d[F]
  4. Se d[F] < d[B] então d[A] < d[D]
  5. NDA

Nenhum comentário:

Postar um comentário