Representación de Grafos

¿Qué es una matriz de adyacencia y cómo se representa?

• Una matriz de adyacencia se representa mediante una estructura de árbol donde se indican las conexiones entre los vértices.

• Una matriz de adyacencia se representa mediante una matriz donde se indican las conexiones entre los vértices con 1 si están conectados y 0 si no lo están.

• Una matriz de adyacencia se representa mediante una tabla hash donde se indican las conexiones entre los vértices.

• Una matriz de adyacencia se representa mediante una lista enlazada donde se indican las conexiones entre los vértices.

Explica cómo se agrega un vértice a una matriz de adyacencia.

• Se agrega una nueva fila y columna en la matriz de adyacencia del grafo.

• Se cambia el valor de un vértice existente en la matriz de adyacencia.

• Se agrega un nuevo vértice al grafo sin modificar la matriz de adyacencia.

• Se elimina una fila y columna en la matriz de adyacencia del grafo.

¿Qué complejidad tiene calcular el grado de un vértice teniendo una matriz de adyacencia?

• O(1)

• O(log n)

• O(n)

• O(n log n)

¿Cuál es una ventaja de utilizar una matriz de adyacencia en la representación de grafos?

• Reduce la complejidad computacional en la búsqueda de caminos mínimos.

• Permite una representación visual más clara del grafo.

• Aumenta la eficiencia en la inserción y eliminación de vértices.

• Facilita la verificación de la existencia de aristas entre vértices.

¿Cuál es una desventaja de utilizar una matriz de adyacencia en la representación de grafos?

• Es más eficiente en términos de tiempo de ejecución

• No permite representar grafos no dirigidos

• Ocupa más espacio en memoria que otras estructuras como listas de adyacencia

• Facilita la búsqueda de vecinos de un vértice

¿Cuál es una ventaja de utilizar listas de adyacencia en la representación de grafos?

• Dificultad para identificar ciclos

• Menor espacio de almacenamiento

• Acceso eficiente a los vecinos de un vértice en particular

• Mayor complejidad en la implementación

¿Cuál es una desventaja de utilizar listas de adyacencia en la representación de grafos?

• Es más difícil determinar si existe una arista entre dos vértices.

• No permiten la implementación de algoritmos de búsqueda eficientes

• Permiten una representación más visual de los grafos

• Son más eficientes en términos de tiempo de ejecución

¿Cuál es la complejidad temporal de agregar un vértice en una matriz de adyacencia?

• O(1)

• O(E^2)

• O(VlogV)

• O(V^2)

¿Cuál es la complejidad temporal de contar los vecinos de un vértice en una lista de adyacencia?

• O(n^2)

• O(log n)

• O(1)

• O(n)

¿Cuál es una situación en la que sería preferible utilizar una matriz de adyacencia en lugar de listas de adyacencia?

• Grafos dispersos

• Grafos densos

• Grafos no ponderados

• Grafos dirigidos