Estructuras de Datos

Un grafo es una representación visual de un conjunto de imágenes conectadas por líneas. Verdadero. Falso.

En un grafo, los vértices también se conocen como nodos. Verdadero. Falso.

En el grafo G=(V,E), "E" representa el conjunto de vértices. Verdadero. Falso.

El eje e=(u,v) conecta dos vértices llamados u y v. Verdadero. Falso.

En el ejemplo dado, los nodos representan carreteras y los ejes representan pueblos. Verdadero. Falso.

Un grafo puede modelar relaciones entre objetos como pueblos conectados por carreteras. Verdadero. Falso.

Un camino en un grafo es cualquier conjunto de vértices, sin importar si están conectados entre sí. Verdadero. Falso.

La longitud de un camino es igual al número de aristas que lo componen. Verdadero. Falso.

En un grafo ponderado, todas las aristas tienen el mismo peso. Verdadero. Falso.

El peso total de un camino en un grafo ponderado se obtiene sumando los pesos de todas sus aristas. Verdadero. Falso.

En un grafo ponderado, las aristas tienen un valor asociado que puede representar, por ejemplo, una distancia entre dos lugares. Verdadero. Falso.

Si un camino tiene 4 vértices, entonces su longitud es necesariamente 4. Verdadero. Falso.

En un grafo dirigido, el eje e=(u,v) es igual al eje e'=(v,u). Verdadero. Falso.

En un grafo dirigido, el eje e=(u,v) indica que u es el origen y v es el destino. Verdadero. Falso.

En un grafo dirigido, si existe un eje de u a v, también se puede ir de v a u automáticamente. Verdadero. Falso.

Un grafo no dirigido no tiene en cuenta el orden de los vértices en sus ejes. Verdadero. Falso.

La diferencia principal entre un grafo dirigido y uno no dirigido es que el primero usa flechas para representar el sentido de la conexión. Verdadero. Falso.

En un grafo no dirigido, e=(u,v) y e=(v,u) se consideran conexiones diferentes. Verdadero. Falso.

En un grafo no dirigido, dos nodos se consideran adyacentes si están conectados por una arista. Verdadero. Falso.

En un grafo dirigido, si existe una arista e=(u,v), entonces u es adyacente hacia v, y v es adyacente desde u. Verdadero. Falso.

Una arista e=(u,v) es incidente solo en el nodo u. Verdadero. Falso.

En un grafo no dirigido, el grado de un vértice es el número de aristas que inciden en él. Verdadero. Falso.

En un grafo dirigido, el grado de un vértice se calcula contando solo las aristas que salen del vértice. Verdadero. Falso.

En un grafo no dirigido, si un vértice tiene grado 3, entonces está conectado con exactamente tres vértices distintos. Verdadero. Falso.

En un grafo dirigido, el grado de entrada de un vértice v es la cantidad de aristas que llegan a v. Verdadero. Falso.

El grado de salida de un vértice v en un grafo dirigido se refiere a la cantidad de aristas que terminan en v. Verdadero. Falso.

Si un vértice tiene grado de entrada 2 y grado de salida 3, entonces hay dos aristas que llegan a él y tres que salen de él. Verdadero. Falso.

En un grafo dirigido, el grado total de un vértice v se puede obtener sumando su grado de entrada y de salida. Verdadero. Falso.

El grado de entrada de un vértice v nunca puede ser mayor que su grado de salida. Verdadero. Falso.

Un camino simple es un recorrido en el grafo en el que no se repite ninguna arista. Verdadero. Falso.

Un ciclo es un camino simple donde el primer vértice y el último coinciden. Verdadero. Falso.

Un grafo es conexo si existe al menos un vértice conectado con todos los demás. Verdadero. Falso.

Un árbol es un grafo que contiene ciclos pero en el que todos los vértices están conectados. Verdadero. Falso.

Todo árbol es un grafo conexo sin ciclos. Verdadero. Falso.

Todo grafo conexo es un árbol. Verdadero. Falso.

La matriz de adyacencia y la lista de adyacencia son dos formas distintas de representar un grafo. Verdadero. Falso.

La lista de adyacencia solo se puede usar con grafos dirigidos. Verdadero. Falso.

La matriz de adyacencia representa las conexiones entre vértices mediante una tabla en la que las filas y columnas corresponden a vértices. Verdadero. Falso.

Las representaciones por matriz y por lista son equivalentes: cualquiera puede usarse para cualquier tipo de grafo. Verdadero. Falso.

La mejor forma de representar un grafo siempre es usando una matriz de adyacencia. Verdadero. Falso.

La matriz de adyacencia de un grafo con n vértices es una tabla de n×n donde se indica si hay o no conexión entre cada par de vértices. Verdadero. Falso.

En una matriz de adyacencia, si matAd[i,j] = 1, eso significa que no existe conexión entre vi y vj. Verdadero. Falso.

Si el grafo es no dirigido, entonces la matriz de adyacencia es simétrica. Verdadero. Falso.

En un grafo dirigido, la matriz de adyacencia siempre es simétrica. Verdadero. Falso.

En una matriz de adyacencia de un grafo ponderado, los valores diferentes de 0 indican el peso de las aristas. Verdadero. Falso.

En cualquier matriz de adyacencia, si matAd[i,j] ≠ 0, entonces hay una arista entre vi y vj. Verdadero. Falso.

En un grafo no dirigido, el grado de un vértice vi se obtiene sumando todos los valores de su fila (o de su columna) en la matriz de adyacencia. Verdadero. Falso.

En un digrafo, el grado de salida de un vértice vi se obtiene sumando todos los valores de la columna i en la matriz de adyacencia. Verdadero. Falso.

En un digrafo, el grado de entrada de un vértice vi se obtiene sumando los valores de la columna i de la matriz de adyacencia. Verdadero. Falso.

En una matriz de adyacencia, el grado total de un vértice vi en un digrafo se puede obtener sumando su fila y su columna. Verdadero. Falso.

La fórmula gradoE(vi) = ∑ A[j, i] sirve para calcular el grado de salida del vértice vi en un digrafo. Verdadero. Falso.

En un grafo no dirigido, es obligatorio sumar tanto la fila como la columna para calcular el grado del vértice. Verdadero. Falso.

La lista de adyacencia asocia a cada vértice una lista de vértices con los que tiene conexión directa. Verdadero. Falso.

En una lista de adyacencia, un vértice v aparece solo si tiene al menos una conexión. Verdadero. Falso.

La lista de adyacencia es más eficiente en memoria que la matriz de adyacencia para grafos dispersos (con pocas conexiones). Verdadero. Falso.

La lista de adyacencia permite recorrer rápidamente todos los vértices adyacentes a un nodo. Verdadero. Falso.

La lista de adyacencia es simétrica en todos los grafos. Verdadero. Falso.

En la lista de adyacencia de un grafo dirigido, cada lista indica los destinos a los que apunta cada vértice. Verdadero. Falso.

En un grafo no dirigido, insertar una arista implica añadir dos entradas en la lista de adyacencia (una para cada vértice). Verdadero. Falso.

En un digrafo, insertar una arista solo requiere añadir una única entrada en la lista de adyacencia. Verdadero. Falso.

La lista de adyacencia es más compacta y ocupa menos espacio para grafos poco densos que la matriz de adyacencia. Verdadero. Falso.

Insertar una arista en una lista de adyacencia es una operación O(1), asumiendo que no se verifica duplicados. Verdadero. Falso.

El grado de un vértice en un grafo no dirigido es el número de elementos en su lista de adyacencia. Verdadero. Falso.

Conocer el número total de ejes en un grafo usando una lista de adyacencia requiere un tiempo O(n + ne), siendo n el número de vértices y ne el número de aristas. Verdadero. Falso.

Para obtener los ejes de salida de un vértice en un digrafo, el tiempo necesario es O(k), donde k es el tamaño de la lista de adyacencia de ese vértice. Verdadero. Falso.

Obtener los ejes de entrada a un vértice en un digrafo usando listas de adyacencia es una operación O(n + ne). Verdadero. Falso.

La implementación típica de la lista de adyacencia para un grafo no dirigido requiere almacenar en la lista de cada vértice todos sus vecinos, añadiendo entradas en ambas listas para cada arista. Verdadero. Falso.

Para implementar un digrafo se recomienda seguir las mismas pautas que para un grafo no dirigido en la lista de adyacencia. Verdadero. Falso.

Para un digrafo, una implementación recomendada es usar la matriz de adyacencia en lugar de la lista de adyacencia. Verdadero. Falso.

El código para implementar un grafo no dirigido con listas de adyacencia debe manejar inserciones dobles para cada arista. Verdadero. Falso.

El recorrido en profundidad (DFS) explora primero los vértices más profundos antes de retroceder. Verdadero. Falso.

El recorrido en anchura (BFS) visita todos los vértices al mismo nivel antes de pasar al siguiente nivel. Verdadero. Falso.

Para realizar un recorrido en un grafo es necesario conocer todos los nodos de antemano. Verdadero. Falso.

Ambos recorridos DFS y BFS pueden utilizarse para numerar o procesar todos los nodos de un grafo. Verdadero. Falso.

Un navegador GPS usa algoritmos similares a DFS o BFS para encontrar rutas. Verdadero. Falso.

El recorrido en profundidad (DFS) es una versión generalizada del recorrido en preorden de un árbol. Verdadero. Falso.

En DFS se comienza siempre por el vértice con menor índice. Verdadero. Falso.

Durante el recorrido DFS, se elige siempre el primer vértice adyacente no visitado para continuar. Verdadero. Falso.

Si no quedan vértices adyacentes no visitados, DFS vuelve al vértice anterior para buscar nuevas opciones. Verdadero. Falso.

El proceso DFS termina cuando se han visitado todos los vértices del grafo, sin importar si están conectados con el nodo inicial. Verdadero. Falso.

En DFS, cada nodo se etiqueta inicialmente como blanco para indicar que no ha sido visitado. Verdadero. Falso.

Un nodo se etiqueta como gris cuando ya ha sido visitado durante el recorrido DFS. Verdadero. Falso.

Para implementar DFS con matriz de adyacencia, se añade un vector de estados para controlar los nodos visitados. Verdadero. Falso.

En DFS implementado sobre matrices de adyacencia, no es necesario utilizar funciones auxiliares o privadas para manejar el recorrido. Verdadero. Falso.

La matriz de adyacencia facilita comprobar rápidamente si existe una arista entre dos nodos en DFS. Verdadero. Falso.

El recorrido en anchura (BFS) es una versión generalizada del recorrido por niveles de un árbol. Verdadero. Falso.

En BFS, primero se visitan los vecinos adyacentes directos al nodo inicial. Verdadero. Falso.

En la siguiente iteración de BFS, se visitan los vecinos de los nodos visitados en la iteración anterior, y así sucesivamente. Verdadero. Falso.

El recorrido BFS suele implementarse con una versión recursiva. Verdadero. Falso.

BFS puede usarse para encontrar la distancia mínima (en número de aristas) desde el nodo inicial a otros nodos. Verdadero. Falso.

Los grafos tienen numerosas aplicaciones en campos como la planificación de trayectorias y juegos de estrategia. Verdadero. Falso.

En un grafo dirigido, el grado de entrada de un vértice es el número de aristas que llegan a ese vértice como destino. Verdadero. Falso.

La matriz de adyacencia de un grafo no dirigido siempre es simétrica. Verdadero. Falso.

En una lista de adyacencia para un digrafo, insertar una arista implica añadir una única entrada en la lista del vértice origen. Verdadero. Falso.

Un camino simple puede repetir vértices pero no aristas. Verdadero. Falso.

El recorrido BFS utiliza una estructura de datos tipo pila para gestionar los nodos a visitar. Verdadero. Falso.

El peso de un camino en un grafo ponderado es la suma de los pesos de todas las aristas que lo componen. Verdadero. Falso.

En la implementación de DFS con matriz de adyacencia, es común usar un vector de estados para controlar los nodos visitados. Verdadero. Falso.

Un grafo conexo es aquel donde existe al menos un camino entre cualquier par de vértices. Verdadero. Falso.

En un grafo no dirigido, el grado de un vértice se calcula contando el número de aristas incidentes en él. Verdadero. Falso.