Fundamentos de Teoría de Grafos: Cuestionarios y Ejercicios Interactivos

Question 1

Entre las siguientes opciones, ¿cuál define correctamente un grafo?

Accepted Answer

Una estructura de datos que consta de un conjunto de vértices y un conjunto de aristas que los conectan.

Answer

Un conjunto de puntos en un plano que se intersecan entre sí.

Answer

Una ecuación que relaciona variables mediante operaciones matemáticas.

Question 2

¿Cuál de las siguientes afirmaciones sobre los vértices de un grafo es verdadera?

Accepted Answer

El grado de un vértice es el número de aristas incidentes a él.

Answer

Los vértices no se pueden desconectar del resto del grafo.

Answer

Todos los vértices deben tener al menos una arista incidente.

Answer

Los vértices no pueden tener bucles.

Question 3

En un grafo dirigido, ¿qué representa cada arista?

Accepted Answer

Una relación unidireccional entre dos vértices.

Answer

Una ruta específica entre dos vértices.

Answer

Una relación bidireccional entre dos vértices.

Answer

Un valor numérico que representa la distancia entre dos vértices.

Question 4

¿Cuál es una condición necesaria para que un grafo sea conexo?

Accepted Answer

Existe un camino entre cada par de vértices.

Answer

El grafo no tiene ciclos.

Answer

El grafo es completo.

Answer

Todos los vértices tienen el mismo grado.

Question 5

En un árbol, ¿qué se garantiza sobre el número de aristas en relación con el número de vértices?

Accepted Answer

El número de aristas es siempre uno menos que el número de vértices.

Answer

El número de aristas puede ser cualquier valor.

Answer

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

Answer

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

Question 6

Entre las siguientes opciones, ¿cuál es una afirmación verdadera sobre los grafos bipartitos?

Accepted Answer

Se pueden dividir los vértices en dos conjuntos disjuntos, de manera que todas las aristas conectan vértices de diferentes conjuntos.

Answer

Los grafos bipartitos no contienen ciclos.

Answer

Todos los grafos bipartitos son conexos.

Answer

Los grafos bipartitos siempre tienen un número par de vértices.

Question 7

¿Cuál de las siguientes afirmaciones sobre grafos completos es cierta?

Accepted Answer

Cada vértice está conectado a todos los demás vértices.

Answer

Los grafos completos son siempre dirigidos.

Answer

Los grafos completos no pueden tener ciclos.

Answer

Un grafo completo tiene el menor número de aristas posible.

Question 8

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

Accepted Answer

El costo o valor asociado con atravesar esa arista.

Answer

La distancia entre los vértices conectados por la arista.

Answer

La capacidad de la arista para transmitir datos.

Answer

El tiempo necesario para atravesar la arista.

Question 9

¿Cuál es el algoritmo utilizado para encontrar el camino más corto entre dos vértices en un grafo ponderado?

Accepted Answer

Algoritmo de Dijkstra

Answer

Algoritmo de Prim

Answer

Algoritmo de Kruskal

Answer

Algoritmo de Floyd-Warshall

Question 10

En la teoría de grafos, ¿cuál es el propósito principal de una matriz de adyacencia?

Accepted Answer

Representar las conexiones entre vértices en un grafo mediante una matriz de ceros y unos.

Answer

Calcular el número de ciclos en un grafo.

Answer

Visualizar el grafo gráficamente.

Answer

Almacenar los pesos de las aristas en un grafo ponderado.

Question 11

Un grafo está formado por:

Accepted Answer

Vértices y aristas

Answer

Polinomios y funciones

Answer

Números y operaciones

Answer

Vectores y subespacios

Question 12

El grado de un vértice representa:

Accepted Answer

El número de aristas conectadas a él

Answer

El número de caminos conectados a él

Answer

El número de componentes conexas conectadas a él

Answer

El número de ciclos conectados a él

Question 13

Un ciclo en un grafo difiere de un camino en que:

Accepted Answer

Comienza y termina en el mismo vértice

Answer

Utiliza todas las aristas distintas

Answer

No tiene vértices repetidos

Answer

Comienza y termina en vértices diferentes

Question 14

Un grafo no dirigido se caracteriza por:

Accepted Answer

Aristas sin dirección

Answer

Aristas con dirección

Answer

Aristas de igual peso

Answer

Aristas de igual longitud

Question 15

Un grafo conexo es aquel en el que:

Accepted Answer

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

Answer

Ningún vértice está conectado por un camino

Answer

Todos los vértices están conectados por un ciclo

Answer

Solo algunos vértices están conectados por un camino

Question 16

El complemento de un grafo G tiene:

Accepted Answer

Los mismos vértices que G y todas las aristas que no están en G

Answer

Los mismos vértices que G y todas las aristas que están en G

Answer

Diferentes vértices que G y todas las aristas que están en G

Question 17

Un grafo consiste en:

Accepted Answer

Vértices y aristas

Answer

Solo vértices

Answer

Solo aristas

Answer

Nodos, aristas y pesos

Question 18

¿Qué representa el grado de un vértice?

Accepted Answer

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

Answer

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

Answer

La longitud del camino más corto desde el vértice a cualquier otro vértice

Answer

El peso total de las aristas incidentes en el vértice

Question 19

Conceptualmente, ¿qué es un camino en un grafo?

Accepted Answer

Una secuencia de vértices conectados por aristas

Answer

Una arista que conecta dos vértices

Answer

Un conjunto de vértices conectados por aristas

Question 20

¿Cuál de las siguientes definiciones describe un ciclo en un grafo?

Accepted Answer

Un camino que comienza y termina en el mismo vértice

Answer

Un camino que contiene todos los vértices del grafo

Answer

Un camino que no contiene vértices repetidos

Question 21

En un grafo dirigido, ¿qué representa una arista?

Accepted Answer

Una relación unilateral entre dos vértices

Answer

Una conexión entre dos vértices con un peso asociado

Answer

Un camino que conecta dos vértices cualesquiera

Answer

Una relación bilateral entre dos vértices

Question 22

¿Qué tipo de grafo tiene todos sus vértices conectados por al menos un camino?

Accepted Answer

Grafo conexo

Answer

Grafo completo

Answer

Grafo acíclico dirigido

Question 23

Un grafo bipartito es aquel que:

Accepted Answer

Se puede dividir en dos conjuntos de vértices de forma que cada arista conecte vértices de distintos conjuntos.

Answer

Tiene todos sus vértices conectados por al menos un camino

Question 24

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

Accepted Answer

La cantidad mínima de colores para colorear los vértices sin que vértices adyacentes tengan el mismo color

Answer

La cantidad máxima de vértices que pueden tener el mismo color

Question 25

Un árbol es un grafo:

Accepted Answer

Conexo y acíclico

Answer

Completo y dirigido

Answer

Bipartito y ponderado

Answer

Euleriano y hamiltoniano

Question 26

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

Accepted Answer

El coste o distancia asociada a la arista

Answer

El tipo de arista (dirigida o no dirigida)

Answer

El número de vértices incidentes a la arista

Answer

La dirección de la arista

Question 27

En el contexto de los grafos, los vértices son:

Accepted Answer

Los puntos finales de las aristas.

Answer

Los componentes conectados del grafo.

Answer

Los segmentos que conectan vértices.

Answer

Las regiones encerradas por aristas.

Question 28

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

Accepted Answer

El número de aristas incidentes en él.

Answer

La suma de los pesos de las aristas incidentes.

Answer

El número de vértices adyacentes.

Question 29

Un ciclo en un grafo es:

Accepted Answer

Un camino cerrado que comienza y termina en el mismo vértice.

Answer

Un conjunto de vértices no conectados por aristas.

Answer

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

Question 30

En un grafo dirigido, ¿cuál es la diferencia entre el grado de entrada y el grado de salida de un vértice?

Accepted Answer

El grado de entrada es el número de aristas que llegan al vértice, mientras que el grado de salida es el número de aristas que salen del vértice.

Answer

El grado de entrada es el grado del vértice, mientras que el grado de salida es el grado del vértice más cercano.

Answer

El grado de entrada y el grado de salida son siempre iguales en un grafo dirigido.

Question 31

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

Accepted Answer

El coste o distancia asociada con la arista.

Answer

La importancia relativa de la arista.

Answer

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

Question 32

En un grafo bipartito, ¿cómo son los conjuntos de vértices?

Accepted Answer

Se pueden dividir en dos conjuntos disjuntos de tal manera que cada arista conecta vértices de diferentes conjuntos.

Answer

Están conectados por un ciclo.

Answer

Tienen el mismo número de vértices.

Question 33

El teorema de Euler para grafos conexos establece que:

Accepted Answer

E = V - 1, donde E es el número de aristas y V el número de vértices.

Answer

V = 2E

Answer

E >= V

Answer

V >= E - 1

Question 34

**Definición de un grafo:** ¿Cuál de las siguientes afirmaciones caracteriza correctamente a un grafo?

Accepted Answer

Un grafo consiste en un conjunto de elementos denominados vértices conectados por otros elementos llamados aristas.

Answer

Un grafo es un diagrama que muestra cómo se relacionan los objetos en un sistema.

Answer

Un grafo es una colección de puntos y líneas que representan relaciones.

Question 35

**Grado de un vértice:** En un grafo, ¿cómo se define el grado de un vértice?

Accepted Answer

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

Answer

El grado es el número de aristas que salen del vértice.

Answer

El grado es el número de vértices conectados al vértice.

Answer

El grado es la suma del número de aristas que entran y salen del vértice.

Question 36

**Caminos en grafos:** ¿Qué se entiende por camino en un grafo?

Accepted Answer

Un camino es una secuencia de vértices y aristas que conecta dos vértices sin repetir ninguno de ellos.

Answer

Un camino es una secuencia de vértices y aristas que conecta dos vértices y puede repetir vértices.

Answer

Un camino es una secuencia de aristas que conecta dos vértices sin repetir ninguna.

Question 37

**Grado promedio de un grafo:** Sea G un grafo con 10 vértices y 15 aristas. ¿Cuál es el grado promedio de los vértices de G?

Accepted Answer

3

Answer

4

Answer

2

Question 38

**Grafos bipartitos:** ¿Cuál es una propiedad distintiva de los grafos bipartitos?

Accepted Answer

Un grafo bipartito se puede dividir en dos conjuntos de vértices de manera que no haya aristas entre los vértices del mismo conjunto.

Answer

Un grafo bipartito siempre es conexo.

Answer

Un grafo bipartito siempre es regular.

Question 39

**Complejidad del algoritmo DFS:** Dada una implementación del algoritmo de recorrido en profundidad (DFS) en un grafo G con n vértices y m aristas, ¿cuál es su complejidad temporal?

Accepted Answer

O(n + m)

Answer

O(m^2)

Answer

O(n^2)

Question 40

¿Qué elementos componen un grafo?

Accepted Answer

Vértices y aristas

Answer

Solo vértices

Answer

Vértices, aristas y pesos

Answer

Solo aristas

Question 41

¿Qué es un camino en un grafo?

Accepted Answer

Una secuencia de vértices conectados por aristas

Answer

Una secuencia de aristas conectadas por vértices

Answer

Una secuencia de vértices y aristas que puede contener repeticiones

Answer

Un conjunto de vértices y aristas no conectados

Question 42

¿Qué es un ciclo en un grafo?

Accepted Answer

Un camino que comienza y termina en el mismo vértice

Answer

Un camino que no contiene ciclos

Answer

Un camino que no tiene vértices repetidos

Answer

Un camino que incluye todos los vértices del grafo

Question 43

En un grafo simple, ¿cuál es el máximo número de aristas que pueden conectar dos vértices?

Accepted Answer

Una

Answer

Tres

Answer

Dos

Answer

Cualquier número

Question 44

En un grafo dirigido, ¿qué característica distingue a las aristas?

Accepted Answer

Tienen dirección

Answer

Tienen peso

Answer

Ninguna de las anteriores

Answer

Tienen color

Question 45

La matriz de adyacencia de un grafo representa:

Accepted Answer

La presencia o ausencia de aristas entre cada par de vértices

Answer

Los pesos de las aristas

Answer

La cantidad de caminos entre cada par de vértices

Answer

Los grados de los vértices

Question 46

El algoritmo de búsqueda en anchura (BFS) explora un grafo:

Accepted Answer

Nivel por nivel, expandiendo los vértices adyacentes

Answer

Por orden de grados de vértices

Answer

En profundidad, explorando un camino completo antes de cambiar

Answer

Aleatoriamente

Question 47

La complejidad temporal del algoritmo de búsqueda en profundidad (DFS) es:

Accepted Answer

O(n+m)

Answer

O(n^2)

Answer

O(n)

Answer

O(m)

Question 48

Los componentes conexos de un grafo son:

Accepted Answer

Subconjuntos de vértices que están conectados entre sí

Answer

Subconjuntos de vértices con grados pares

Answer

Subconjuntos de vértices con caminos más cortos entre ellos

Answer

Subconjuntos de vértices que comparten un vértice común