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
ABCDE

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

deg = 2
  1. 1A
  2. 2B
  3. 3C
  4. 4D
  5. 5E
2.Fácil

¿Cuántas aristas, |E|, tiene el grafo completo K6?

K6
|E| =
3.Media

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

3 × deg 33 × deg 43 × deg 5
L =
4.Media

Un grafo conexo tiene 9 vértices y 9 aristas. ¿Cuántas aristas, k, hay que quitar para obtener un árbol generador?

|V| = 9|E| = 9
k =
5.Difícil
101312141411163ABCDEFG

El algoritmo de Kruskal construye un árbol generador mínimo. Haz clic en la arista que añade como arista número 6; las aristas descartadas no cuentan.

k = 6
  1. 1arista AC
  2. 2arista BC
  3. 3arista BD
  4. 4arista CE
  5. 5arista DF
  6. 6arista EF
  7. 7arista GB
  8. 8arista GC
  9. 9arista GD
6.Difícil
151212671513410ABCDEFG

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

inicio: Aronda 3
  1. 1A
  2. 2B
  3. 3C
  4. 4D
  5. 5E
  6. 6F
  7. 7G

Soluciones

  1. 1. A
  2. 2. |E| = 15
  3. 3. L = 20
  4. 4. k = 1
  5. 5. arista BC
  6. 6. E

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