Caminos y ciclos en grafos: cuestionarios interactivos para Matemáticas Discretas

Question 1

Define un camino en un grafo. Indica qué características debe cumplir.

Accepted Answer

Una secuencia de vértices conectados por aristas contiguas.

Answer

Una secuencia de vértices que comienza y termina en el mismo vértice.

Answer

Un conjunto de vértices conectados por aristas cualesquiera.

Question 2

¿Qué algoritmo se utiliza principalmente para encontrar ciclos en grafos no dirigidos?

Accepted Answer

Búsqueda en profundidad (DFS)

Answer

Búsqueda en anchura (BFS)

Answer

Algoritmo de Floyd-Warshall

Answer

Algoritmo de Dijkstra

Question 3

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

Accepted Answer

Existe al menos un camino entre cada par de vértices.

Answer

No contiene ciclos.

Answer

Solo tiene un vértice.

Question 4

¿Qué teorema relaciona caminos y ciclos en un grafo?

Accepted Answer

Teorema de Euler

Answer

Teorema de Cayley

Answer

Teorema de Kuratowski

Answer

Teorema de Hamilton

Question 5

¿Cómo se caracteriza un ciclo en un grafo en términos del número de vértices y aristas?

Accepted Answer

Número de vértices igual al número de aristas

Answer

Número de vértices mayor que el número de aristas

Answer

Número de aristas igual a cero

Answer

Número de vértices menor que el número de aristas

Question 6

Define un camino simple en un grafo.

Accepted Answer

Un camino que no contiene vértices repetidos.

Answer

Un camino con el número máximo de aristas.

Answer

Un camino que pasa por todos los vértices del grafo.

Answer

Un camino que representa la ruta más corta entre dos vértices.

Question 7

¿Cuál es la función del algoritmo de Floyd-Warshall?

Accepted Answer

Encontrar las distancias más cortas entre todos los pares de vértices en un grafo ponderado.

Answer

Identificar los caminos más cortos en un grafo.

Answer

Detectar los ciclos más cortos en un grafo.

Question 8

¿Qué caracteriza a un grafo que es un árbol?

Accepted Answer

Es conexo y acíclico.

Answer

Contiene todas las aristas posibles.

Answer

Tiene un único vértice.

Question 9

¿Cuál de los siguientes algoritmos se utiliza para encontrar el camino más corto entre dos nodos en un grafo no dirigido y ponderado?

Accepted Answer

Algoritmo de Dijkstra

Answer

Búsqueda en amplitud

Answer

Algoritmo de Bellman-Ford

Answer

Algoritmo de Floyd-Warshall

Question 10

¿Cuál de las siguientes propiedades de un grafo implica que es acíclico?

Accepted Answer

No tiene ciclos

Answer

Es conexo

Answer

Es bipartito

Answer

Tiene un número par de aristas

Question 11

Un grafo con n vértices y m aristas es conexo si:

Accepted Answer

Existe un camino entre cualquier par de vértices del grafo.

Answer

El grafo es dirigido.

Answer

El número de componentes conexas es n.

Answer

El número de aristas es mayor que el número de vértices.

Question 12

¿Cuál de las siguientes afirmaciones sobre los ciclos hamiltonianos es cierta?

Accepted Answer

Son ciclos que recorren todos los vértices del grafo exactamente una vez.

Answer

Tienen un peso menor que cualquier otro ciclo que contenga los mismos vértices.

Answer

Siempre existen en cualquier grafo conexo.

Question 13

En un grafo dirigido, un ciclo dirigido es un camino que:

Accepted Answer

Comienza y termina en el mismo vértice.

Answer

Contiene todos los vértices del grafo.

Answer

Es un camino más corto entre dos vértices.

Answer

Tiene al menos una arista con peso negativo.

Question 14

El problema del camino del vendedor viajero consiste en encontrar:

Accepted Answer

El ciclo más corto que visita todos los vértices de un grafo ponderado exactamente una vez.

Answer

El camino más largo que conecta dos vértices específicos.

Answer

El conjunto mínimo de aristas que conecta todos los vértices de un grafo.

Question 15

En un grafo ponderado, un árbol de expansión es un:

Accepted Answer

Subgrafo conexo que incluye todos los vértices del grafo original y tiene el peso total mínimo.

Answer

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

Answer

Conjunto de aristas que forma un camino del vendedor viajero.

Question 16

Un ciclo hamiltoniano es un ciclo que visita cada vértice del grafo exactamente una vez. ¿Verdadero o Falso?

Accepted Answer

Verdadero

Answer

Solo si el grafo es euleriano

Answer

Solo si el grafo es fuertemente conexo

Answer

Falso

Question 17

Para encontrar caminos más cortos en un grafo con pesos, ¿cuál de los siguientes algoritmos se utiliza?

Accepted Answer

Algoritmo de Dijkstra

Answer

Algoritmo de Kruskal

Answer

Algoritmo de Prim

Question 18

Un grafo bipartito es un grafo cuyos vértices pueden dividirse en dos conjuntos disjuntos, de forma que no haya aristas entre vértices del mismo conjunto. ¿Verdadero o Falso?

Accepted Answer

Verdadero

Answer

Solo si el grafo es conexo

Answer

Solo si el grafo es regular

Answer

Falso

Question 19

Un grafo conexo es aquel en el que todos los pares de vértices están conectados por un camino. ¿Verdadero o Falso?

Accepted Answer

Verdadero

Answer

Todos los pares de vértices están conectados por una arista

Answer

El grafo tiene al menos un ciclo

Question 20

Un árbol es un grafo conexo y acíclico. ¿Verdadero o Falso?

Accepted Answer

Verdadero

Answer

Solo si el grafo es regular

Answer

Falso

Answer

Solo si el grafo es bipartito

Question 21

Un grafo sin ciclos es conocido como:

Accepted Answer

Árbol

Answer

Grafo bipartito

Answer

Grafo estrella

Answer

Grafo completo

Question 22

Un camino en el que se pueden visitar los mismos vértices y aristas múltiples veces se conoce como:

Accepted Answer

Caminata

Answer

Falso

Answer

Solo si el grafo es euleriano

Answer

Solo si el grafo es acíclico

Question 23

Un grafo dirigido de n nodos y m aristas es fuertemente conexo si:

Accepted Answer

Para cualquier par de nodos (a, b) existe un camino de a a b y de b a a

Answer

Todos los nodos tienen el mismo grado

Answer

No hay ciclos en el grafo

Question 24

El algoritmo de búsqueda en profundidad (DFS) visita los nodos de un grafo en el orden en que son:

Accepted Answer

Descubiertos

Answer

Visitados

Answer

Procesados

Answer

Completados

Question 25

Un ciclo en un grafo es:

Accepted Answer

Un camino cerrado que comienza y termina en el mismo nodo

Answer

Un conjunto de aristas que conectan un nodo consigo mismo

Answer

Un camino que no contiene nodos repetidos

Question 26

El algoritmo de Floyd-Warshall calcula:

Accepted Answer

Las distancias más cortas entre todos los pares de nodos en un grafo ponderado

Answer

Los caminos más cortos entre todos los pares de nodos en un grafo no dirigido

Answer

Los ciclos más cortos en un grafo dirigido

Question 27

Un grafo se dice que es planar si:

Accepted Answer

Puede representarse en un plano sin que sus aristas se crucen

Answer

Es un grafo conexo

Answer

Tiene un número impar de nodos

Answer

Es un grafo acíclico

Question 28

Un grafo completo de n nodos tiene como máximo:

Accepted Answer

n*(n-1)/2 aristas

Answer

m*(m-1)/2 aristas

Answer

n*(n+1)/2 aristas

Answer

m*(m+1)/2 aristas

Question 29

El algoritmo de Dijkstra calcula:

Accepted Answer

El camino más corto desde un nodo origen a todos los demás nodos en un grafo ponderado

Answer

Los ciclos más cortos en un grafo dirigido

Answer

Los componentes conexas en un grafo

Question 30

Un árbol de expansión mínima (MST) de un grafo ponderado es:

Accepted Answer

Un subgrafo que conecta todos los nodos del grafo y tiene el peso total mínimo

Answer

Un subgrafo que tiene el mayor número de aristas posible

Answer

Un ciclo que pasa por todos los nodos

Question 31

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

Accepted Answer

Grafo ciclo

Answer

Grafo regular

Answer

Grafo dirigido

Answer

Grafo bipartito

Question 32

Para encontrar el camino más corto entre dos vértices en un grafo sin pesos, ¿qué algoritmo de búsqueda se utiliza?

Accepted Answer

Algoritmo de búsqueda en amplitud (BFS)

Answer

Algoritmo de Dijkstra

Answer

Algoritmo de Bellman-Ford

Answer

Algoritmo de Floyd-Warshall

Question 33

¿Cuál de las siguientes propiedades es característica de los grafos planares?

Accepted Answer

Pueden dibujarse en un plano sin que sus aristas se crucen

Answer

Tienen todos sus vértices de grado impar

Answer

Son siempre grafos conexos

Answer

Son siempre grafos bipartitos

Question 34

Dos grafos se denominan isomorfos si:

Accepted Answer

Tienen el mismo número de vértices y aristas, y la relación de adyacencia es la misma

Answer

Tienen los mismos colores y etiquetas

Answer

Tienen el mismo nombre y descripción

Answer

Tienen la misma forma y tamaño

Question 35

En un grafo con n vértices y m aristas, el número mínimo de aristas que se deben eliminar para obtener un bosque es:

Accepted Answer

m - n + 1

Answer

n - m + 1

Answer

m - 2 * n + 1

Answer

m + n - 1

Question 36

Un grafo es conexo si...

Accepted Answer

Existe un camino entre cualquier par de vértices.

Answer

Es un árbol.

Answer

Todos sus vértices tienen el mismo grado.

Answer

No contiene ciclos.

Question 37

Un camino que empieza y termina en el mismo vértice se llama:

Accepted Answer

Ciclo

Answer

Camino Euleriano

Answer

Camino simple

Answer

Camino Hamiltoniano

Question 38

Un camino Euleriano en un grafo es un camino que...

Accepted Answer

Visita cada arista exactamente una vez.

Answer

Visita cada vértice exactamente una vez.

Answer

Es el camino más corto entre dos vértices.

Question 39

Un grafo tiene un camino Euleriano si y solo si:

Accepted Answer

Todos sus vértices tienen grado par, o exactamente dos vértices tienen grado impar.

Answer

Todos sus vértices tienen grado impar.

Answer

Es un grafo completo.

Question 40

Un camino Hamiltoniano en un grafo es un camino que...

Accepted Answer

Visita cada vértice exactamente una vez.

Answer

Visita cada arista exactamente una vez.

Answer

Es el camino más corto entre dos vértices.

Question 41

El problema de encontrar un camino Hamiltoniano en un grafo es:

Accepted Answer

NP-completo.

Answer

Siempre tiene una solución.

Answer

Fácil de resolver para grafos grandes.

Answer

Puede resolverse en tiempo polinomial.

Question 42

El algoritmo de Dijkstra se utiliza para:

Accepted Answer

Encontrar el camino más corto entre dos vértices en un grafo ponderado.

Answer

Encontrar un camino Euleriano.

Answer

Encontrar un camino Hamiltoniano.

Question 43

El algoritmo de búsqueda en anchura (BFS) se utiliza para:

Accepted Answer

Encontrar todos los vértices conectados a un vértice inicial.

Answer

Encontrar un camino Euleriano.

Answer

Encontrar el camino más corto entre dos vértices.

Question 44

La búsqueda en profundidad (DFS) es útil para:

Accepted Answer

Detectar ciclos en un grafo.

Answer

Encontrar un camino Euleriano.

Answer

Encontrar el camino más corto entre dos vértices.

Answer

Determinar si un grafo es bipartito.

Question 45

Un árbol de expansión mínima (MST) en un grafo ponderado es:

Accepted Answer

Un árbol que conecta todos los vértices con el peso total de las aristas mínimo.

Answer

Un árbol que tiene el mayor número de aristas posibles.

Answer

Un árbol que contiene todos los vértices con la mayor cantidad de aristas.