Um grafo é uma representação gráfica de elementos de dados e das conexões ou ausência de conexões entre eles. Várias situações do mundo real podem ser representadas como grafos: diagramas de organizações, mapas rodoviários, redes em geral: sociais, energia elétrica, água e esgoto, computadores, transporte, comunicações (satélites, telefonia com fio e sem fio), entre outras aplicações.

Busca em um grafo é um processo de visitar todos os vértices de um grafo, mesmo que neste processo sejam visitados mais de uma vez as arestas e/ou os vértices.

Considere o grafo da figura a seguir: (ANEXO)

Considere que representa uma rede de computadores ponto-a-ponto. O computador J que ele se desconectou da rede. Além disso, também ocorreu um defeito na comunicação entre N e Q. E sobre os algoritmos de busca a partir de N, julgue as afirmações em (V) verdadeiras e (F) falsas.

( ) O vértice M é o último a ser visitado na busca em profundidade.

( ) Para alcançar P, o algoritmo de busca em largura visitará 3 vértices e o algoritmo de busca em profundidade visitará 4 vértices.

( ) Se o vértice Q é removido, ambos os algoritmos visitarão os vértices na mesma ordem.

( ) Se o objetivo for encontrar K, o algoritmo busca em profundidade encontrará com menos visitas que o algoritmo de busca em largura.

( ) Se o vértice N for removido e o início passa a ser K, a ordem dos vértices visitados com ambos os algoritmos de busca é igual.

Assinale a alternativa que apresenta a seque^ncia correta.

Alternativas:

a) V – F – V – F – V.

b) F – F – V – V – V.

c) V – V – F – V – F.

d) V – V – F – F – V.

e) F – V – V – V – F.