Question

Suponha que os vizinhos de um vértice, durante a execução do DFS, são sempre listados na ordem Norte, Leste, Sul, Oeste, onde os pontos cardeais correspondem a uma realização do grafo sobre um sistema de coordenadas da forma trivial: o vértice (i,j) será colocado na coordenada (i,j), a primeira coordenada corresponde ao eixo Oeste (-) Leste (+), e a segunda ao eixo Sul (-) Norte (+), ainda correspondendo à figura anterior. Suponha que o DFS inicia no vértice (1,1), e aplicamos a operação de contração sobre a árvore de busca DFS. Podemos afirmar:

Accepted Answer

A) A árvore de busca DFS contraída tem profundidade O(1) e número de vértices O(1).

Answer

B) A árvore de busca DFS contraída tem profundidade Ω(log n) e número de vértices Ω(1).

Answer

C) A árvore de busca DFS contraída tem profundidade Ω(log n) e número de vértices Ω(log n).

Answer

D) A árvore de busca DFS contraída tem profundidade Ω(log n) e número de vértices Ω(n).

Answer

E) A árvore de busca DFS contraída tem profundidade Ω(n) e número de vértices Ω(n).

Mais questões de Árvores e grafos