Introducción a los grafos: conceptos básicos para estudiantes de Ingeniería Informática

Question 1

En un grafo no dirigido, el grado de un vértice es:

Accepted Answer

El número de aristas que inciden en el vértice

Answer

El número de aristas que conectan al vértice con todos los demás vértices

Answer

El número de arcos que inciden en el vértice

Answer

El número de vértices adyacentes al vértice

Question 2

Una propiedad de los grafos completos es:

Accepted Answer

Para n vértices, hay n*(n-1)/2 aristas

Answer

Todos los vértices están conectados por una única arista

Answer

No hay ciclos en el grafo

Question 3

En un grafo bipartito, las particiones de los vértices se denominan:

Accepted Answer

Partes

Answer

Subgrafos

Answer

Clústeres

Answer

Componentes

Question 4

Una propiedad de los grafos regulares es:

Accepted Answer

Todos los vértices tienen el mismo grado

Answer

El grado de un grafo regular es igual al número de vértices

Answer

Todos los grafos regulares son grafos completos

Answer

Los grafos regulares no pueden contener ciclos

Question 5

Un grafo conexo es aquel en el que:

Accepted Answer

Existe un camino entre todos los pares de vértices

Answer

Todos los vértices están conectados directamente

Answer

No hay ciclos en el grafo

Question 6

¿Cuál de las siguientes técnicas NO se utiliza para representar grafos?

Accepted Answer

Lista de adyacencia circular

Answer

Lista de adyacencia

Answer

Matriz de adyacencia

Question 7

¿Cuál es la definición precisa de un grafo?

Accepted Answer

Una estructura matemática que consta de un conjunto de vértices (nodos) y un conjunto de aristas (conexiones) que unen estos vértices.

Answer

Una ecuación que describe la relación entre dos o más variables.

Answer

Una representación visual de un proceso mediante diagramas de flujo.

Question 8

¿Qué tipo de grafo se caracteriza por tener un camino que conecta todos sus vértices?

Accepted Answer

Grafo conexo

Answer

Grafo plano

Answer

Grafo acíclico dirigido

Answer

Grafo completo

Question 9

¿Cuál de las siguientes afirmaciones describe correctamente las aristas en un grafo dirigido?

Accepted Answer

Tienen una dirección definida, indicada por una flecha.

Answer

No pueden formar ciclos en el grafo.

Answer

Siempre conectan vértices con el mismo grado.

Answer

Son bidireccionales, lo que permite el flujo en ambas direcciones.

Question 10

¿Qué tipo de grafo es adecuado para modelar redes sociales donde los nodos representan individuos y las aristas indican conexiones?

Accepted Answer

Grafo social

Answer

Grafo etiquetado

Answer

Grafo plano

Answer

Grafo ponderado

Question 11

¿Cuál es el algoritmo más eficiente para encontrar la ruta más corta entre dos vértices en un grafo ponderado?

Accepted Answer

Algoritmo de Dijkstra

Answer

Algoritmo de Prim

Answer

Algoritmo de Floyd-Warshall

Answer

Algoritmo de Kruskal

Question 12

En términos de complejidad temporal, ¿cuál es el orden de crecimiento del algoritmo de Kruskal para encontrar un árbol de expansión mínima?

Accepted Answer

O(E log V)

Answer

O(V log V)

Answer

O(V)

Answer

O(E)

Question 13

¿Qué propiedad asegura que un grafo no dirigido está conectado?

Accepted Answer

Todos los pares de vértices están conectados por al menos un camino.

Answer

El grafo tiene un único vértice.

Answer

El grafo es plano.

Answer

El grafo es regular.

Question 14

¿Cuál de las siguientes afirmaciones es FALSA sobre los grafos?

Accepted Answer

Un grafo puede tener bucles pero no aristas múltiples.

Answer

Un grafo es una estructura que consiste en un conjunto de vértices y aristas.

Answer

Las aristas conectan pares de vértices.

Question 15

¿Qué tipo de grafo tiene aristas con dirección?

Accepted Answer

Grafo dirigido

Answer

Grafo no dirigido

Answer

Grafo simple

Answer

Grafo ponderado

Question 16

Un grafo en el que cada par de vértices está conectado por una arista se llama:

Accepted Answer

Grafo completo

Answer

Grafo bipartito

Answer

Grafo conexo

Answer

Grafo regular

Question 17

¿Qué describe el grado de un vértice en un grafo?

Accepted Answer

El número de aristas que inciden en el vértice.

Answer

La distancia más corta a cualquier otro vértice.

Answer

El número de vértices adyacentes.

Answer

El peso total de las aristas incidentes.

Question 18

¿Qué es un camino en un grafo?

Accepted Answer

Una secuencia de vértices conectados por aristas.

Answer

Un conjunto de vértices conectados.

Answer

Un ciclo que pasa por todos los vértices.

Answer

Un conjunto de aristas que no forman un ciclo.

Question 19

¿Cuándo se dice que un grafo es conexo?

Accepted Answer

Si existe un camino entre cada par de vértices.

Answer

Si tiene un número par de vértices.

Answer

Si no tiene ciclos.

Answer

Si todos los vértices tienen el mismo grado.

Question 20

Un grafo que no tiene ciclos se llama:

Accepted Answer

Grafo acíclico

Answer

Grafo conexo

Answer

Grafo bipartito

Answer

Grafo completo

Question 21

¿Qué es un árbol?

Accepted Answer

Un grafo conexo y acíclico.

Answer

Un grafo bipartito con dos conjuntos de vértices.

Answer

Un grafo dirigido sin ciclos.

Answer

Un grafo completo con n-1 aristas.

Question 22

En un grafo ponderado, ¿qué representa el peso de una arista?

Accepted Answer

Un valor asociado a la arista, como la distancia o el costo.

Answer

La dirección de la arista.

Answer

El número de vértices conectados por la arista.

Question 23

¿Qué tipo de grafo es aquel en el que todos sus vértices están conectados por exactamente una arista?

Accepted Answer

Grafo completo

Answer

Grafo bipartito

Answer

Grafo regular

Answer

Grafo acíclico

Question 24

¿Cuál de las siguientes propiedades NO es aplicable a un grafo no dirigido?

Accepted Answer

Grado de entrada

Answer

Grado máximo

Answer

Camino

Answer

Grado

Question 25

¿Qué algoritmo se utiliza para encontrar el camino más corto entre dos vértices en un grafo ponderado?

Accepted Answer

Algoritmo de Dijkstra

Answer

Algoritmo de Floyd-Warshall

Answer

Algoritmo de Prim

Answer

Algoritmo de Kruskal

Question 26

¿Cuál es la complejidad temporal del algoritmo de ordenación topológica?

Accepted Answer

O(V + E)

Answer

O(E²)

Answer

O(E log V)

Answer

O(V^2)

Question 27

¿Qué teorema establece que el número de aristas en un grafo conexo es siempre menor que el número de vértices?

Accepted Answer

Teorema de Erdős-Gallai

Answer

Teorema de Euler

Answer

Teorema de König

Answer

Teorema de Kuratowski

Question 28

¿Qué tipo de grafo es aquel en el que todas sus aristas tienen el mismo peso?

Accepted Answer

Grafo uniforme

Answer

Grafo regular

Answer

Grafo completo

Answer

Grafo ponderado

Question 29

¿Cuál es el grado de un vértice que está conectado a n otros vértices?

Accepted Answer

n

Answer

n / 2

Answer

n + 1

Answer

n - 1

Question 30

¿Qué teorema establece que todo grafo conexo con n vértices y m aristas cumple la relación n - 1 ≤ m ≤ n(n - 1) / 2?

Accepted Answer

Teorema de Mantel

Answer

Teorema de König

Answer

Teorema de Kuratowski

Answer

Teorema de Euler

Question 31

Indica cuál de las siguientes afirmaciones es verdadera para un grafo no dirigido:

Accepted Answer

El número de aristas es siempre par.

Answer

El grado de cada vértice es siempre par.

Answer

El número de vértices es siempre impar.

Answer

El número de componentes conexas es siempre igual al número de vértices.

Question 32

El número cromático de un grafo es:

Accepted Answer

El número mínimo de colores necesarios para colorear los vértices de manera que ningún vértice adyacente tenga el mismo color.

Answer

El número máximo de aristas que puede tener un grafo.

Question 33

Un grafo es bipartito si:

Accepted Answer

Sus vértices se pueden dividir en dos conjuntos disjuntos de manera que todas las aristas tengan un extremo en cada conjunto.

Answer

Todos sus vértices tienen el mismo grado.

Question 34

El grado de un vértice en un grafo es:

Accepted Answer

El número de aristas incidentes al vértice.

Answer

El número de ciclos que pasan por el vértice.

Answer

El número de vértices adyacentes al vértice.

Answer

El número de componentes conexas que contiene el vértice.

Question 35

Un grafo dirigido es fuerte si:

Accepted Answer

Existe un camino dirigido desde cualquier vértice a cualquier otro.

Answer

Sus vértices están ordenados topológicamente.

Answer

Todos sus vértices tienen el mismo grado de entrada.

Question 36

El teorema de Euler establece que en un grafo conexo:

Accepted Answer

El número de vértices con grado impar es siempre par.

Answer

Siempre existe un ciclo hamiltoniano.

Answer

El número de componentes conexas es siempre igual al número de vértices.

Question 37

Un camino hamiltoniano en un grafo es:

Accepted Answer

Un camino que visita todos los vértices del grafo exactamente una vez.

Answer

Un ciclo que visita todos los vértices del grafo exactamente una vez.

Answer

Un camino que visita todos los vértices del grafo al menos una vez.

Question 38

Una gráfica plana es:

Accepted Answer

Una gráfica que se puede dibujar en un plano sin que sus aristas se crucen.

Answer

Una gráfica que es bipartita.

Answer

Una gráfica que es conexa.

Question 39

¿Cuál de las siguientes afirmaciones es verdadera sobre un grafo?

Accepted Answer

Es un conjunto de vértices y aristas

Answer

Es un conjunto de aristas y vértices

Answer

Es un conjunto de vértices y nodos

Answer

Es un conjunto de nodos y enlaces

Question 40

¿Cuál de los siguientes tipos de grafos no tiene aristas dirigidas?

Accepted Answer

Grafo no dirigido

Answer

Pseudografo

Answer

Grafo dirigido

Answer

Hipergrafo

Question 41

¿Cuál de las siguientes propiedades es cierta para un grafo conexo?

Accepted Answer

Cualquier par de vértices está conectado por un camino

Answer

El grafo no tiene ciclos

Answer

El grafo tiene al menos un ciclo

Question 42

¿Cuál de las siguientes afirmaciones es verdadera sobre el grado de un vértice?

Accepted Answer

Es el número de aristas incidentes en el vértice

Answer

Es el número de vértices adyacentes al vértice

Answer

Es el número de aristas que conectan el vértice con otros vértices

Answer

Es el número de caminos desde el vértice a cualquier otro vértice

Question 43

¿Cuál de los siguientes algoritmos se utiliza para encontrar el camino más corto entre dos vértices?

Accepted Answer

Algoritmo de Dijkstra

Answer

Algoritmo de Prim

Answer

Algoritmo de Floyd-Warshall

Answer

Algoritmo de Kruskal

Question 44

¿Cuál de las siguientes representaciones de un grafo es más compacta?

Accepted Answer

Matriz de adyacencia

Answer

Representación gráfica

Answer

Lista de adyacencia

Answer

Lista de incidencias

Question 45

¿Cuál de las siguientes afirmaciones es verdadera sobre un árbol?

Accepted Answer

Es un grafo conexo y acíclico

Answer

Es un grafo no dirigido y no conexo

Answer

Es un grafo dirigido y conexo

Answer

Es un grafo dirigido y no conexo

Question 46

¿Cuál de los siguientes es un problema clásico de teoría de grafos?

Accepted Answer

Problema del viajante

Answer

Problema de enrutamiento

Answer

Problema de asignación

Answer

Problema de la mochila

Question 47

¿Cuál de las siguientes afirmaciones es verdadera sobre el algoritmo de ordenación topológica?

Accepted Answer

Se utiliza para ordenar los vértices de un grafo dirigido acíclico

Answer

Se utiliza para encontrar un ciclo Hamiltoniano en un grafo

Answer

Se utiliza para encontrar el camino más corto entre dos vértices

Question 48

¿Cuál de las siguientes afirmaciones es verdadera sobre el teorema de Euler?

Accepted Answer

Establece una condición necesaria y suficiente para que un grafo tenga un ciclo Euleriano

Answer

Establece una condición necesaria y suficiente para que un grafo sea acíclico

Answer

Establece una condición necesaria y suficiente para que un grafo sea conexo