Hoja de ejercicios de Teoría de grafos con soluciones

Hoja de ejercicios de Teoría de grafos gratis e imprimible: 6 problemas desde nivel fácil hasta nivel de examen, con soluciones. Imprímela o guárdala como PDF.

Nueva hoja de ejerciciosPractica en línea con pistas

Para docentes: pueden imprimirla, copiarla y usarla en clase gratis. Cada hoja nueva tiene valores nuevos y su propia clave de respuestas. Agradecemos un enlace a ExamProblems en la página de tu curso.

Nombre: ____________________   Fecha: ____________

1.Fácil

Un árbol tiene 34 vértices. ¿Cuántas aristas, |E|, tiene?

|V| = 34
|E| =
2.Fácil
ABCDE

Exactamente un vértice del grafo tiene grado 3. Haz clic en él.

deg = 3
  1. 1A
  2. 2B
  3. 3C
  4. 4D
  5. 5E
3.Media

Un árbol tiene 2 vértices de grado 3, 4 vértices de grado 4, 4 vértices de grado 2, y todos sus demás vértices son hojas (grado 1). ¿Cuántas hojas, L, tiene?

2 × deg 34 × deg 44 × deg 2
L =
4.Media
ABCDEFGCircuito eulerianoCamino euleriano, sin circuitoninguna de las dos

¿Tiene el grafo conexo un circuito euleriano, un camino euleriano que no es un circuito, o ninguno de los dos? Haz clic en tu respuesta.

|V| = 7|E| = 8
  1. 1Circuito euleriano
  2. 2Camino euleriano, sin circuito
  3. 3ninguna de las dos
5.Difícil
2158145101014711ABCDEFG

El algoritmo de Dijkstra se ejecuta desde A. Haz clic en el vértice que se fija (se hace permanente) en la ronda 5; la propia A es la ronda 1.

inicio: Aronda 5
  1. 1A
  2. 2B
  3. 3C
  4. 4D
  5. 5E
  6. 6F
  7. 7G
6.Difícil
19217115719ABCDEF

El algoritmo de Prim construye un árbol generador mínimo a partir del vértice F. Haz clic en la arista que añade como arista número 5.

inicio: Fk = 5
  1. 1arista AC
  2. 2arista BC
  3. 3arista BD
  4. 4arista CE
  5. 5arista DE
  6. 6arista DF
  7. 7arista EF
  8. 8arista BE

Soluciones

  1. 1. |E| = 33
  2. 2. E
  3. 3. L = 12
  4. 4. Camino euleriano, sin circuito
  5. 5. E
  6. 6. arista AC

Soluciones completas paso a paso: practica este tema en examproblems.com.