Test sobre Grafo y búsqueda en anchura y en profundidad

Pregunta 1: La representación de grafos mediante una matriz de adyacencia siempre es eficiente en términos de espacio de almacenamiento, independientemente de la densidad del grafo.

A. Sí

B. No

Explicación: La matriz de adyacencia requiere un espacio de almacenamiento de O(V²) incluso para grafos dispersos (con pocas aristas), lo que puede ser ineficiente si V es muy grande y el número de aristas es pequeño.

Pregunta 2: ¿Cuál de las siguientes afirmaciones describe correctamente una ventaja de utilizar una matriz de adyacencia para representar un grafo?

A. Permite verificar rápidamente la existencia de una arista entre dos vértices en tiempo constante (O(1)).

B. Es eficiente en términos de espacio de almacenamiento para grafos dispersos.

C. Iterar sobre los vecinos de un vértice se realiza en tiempo constante (O(1)).

D. Su eficiencia es notable en grafos densos (con muchas aristas).

Explicación: Según los materiales de estudio, las ventajas de la matriz de adyacencia son que 'Permite verificar rápidamente la existencia de una arista entre dos vértices (O(1))' y que 'Es eficiente para grafos densos (con muchas aristas)'. La opción 1 refleja la primera ventaja y la opción 4 refleja la segunda. La opción 2 es incorrecta porque requiere un espacio de almacenamiento de O(V²) y es ineficiente para grafos dispersos. La opción 3 es incorrecta porque iterar sobre los vecinos de un vértice requiere O(V) tiempo.

Pregunta 3: Verificar la existencia de una arista entre dos vértices en una lista de adyacencia siempre se puede realizar en tiempo constante, independientemente del grado del vértice.

A. Sí

B. No

Explicación: La desventaja de las listas de adyacencia es que verificar la existencia de una arista entre dos vértices puede requerir O(grado(v)) tiempo en el peor caso, no siempre tiempo constante.

Pregunta 4: La lista de adyacencia requiere un espacio de almacenamiento de O(V + E), siendo más eficiente para grafos dispersos.

A. Sí

B. No

Explicación: Según los materiales de estudio, una ventaja de la lista de adyacencia es que requiere un espacio de almacenamiento de O(V + E), lo que la hace más eficiente para grafos dispersos.

Pregunta 5: ¿Cuál de las siguientes afirmaciones es correcta con respecto a la representación de un grafo dirigido mediante una lista de adyacencia, si existe una arista del vértice 'i' al vértice 'j'?

A. El vértice 'j' estará en la lista de adyacencia del vértice 'i'.

B. El vértice 'i' necesariamente estará en la lista de adyacencia del vértice 'j'.

C. Tanto el vértice 'i' como el 'j' aparecerán en la lista de adyacencia del otro.

D. La existencia de la arista se representa solo si el grafo es ponderado.

Explicación: Según el material de estudio, para un grafo dirigido, si existe una arista de 'i' a 'j', entonces 'j' estará en la lista de adyacencia de 'i'. Sin embargo, 'i' no necesariamente estará en la lista de adyacencia de 'j', lo cual invalida las opciones que sugieren reciprocidad o necesidad de aparición de 'i' en la lista de 'j'. La ponderación del grafo solo afecta a la información adicional almacenada, no a la representación básica de la arista.