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 bosque (un grafo sin ciclos) tiene 40 vértices y 4 componentes conexas. ¿Cuántas aristas, |E|, tiene?

|V| = 40c = 4
|E| =
2.Fácil

Un grafo simple tiene 7 vértices con grados 4, 3, 3, 2, 2, 1, 1. ¿Cuántas aristas, |E|, tiene?

deg: 4, 3, 3, 2, 2, 1, 1
|E| =
3.Media

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

3 × deg 34 × deg 43 × deg 54 × deg 2
L =
4.Media

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

3 × deg 42 × deg 5
L =
5.Difícil
1018126191319ABCDEF

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

k = 4
  1. 1arista AC
  2. 2arista BC
  3. 3arista BD
  4. 4arista CE
  5. 5arista DE
  6. 6arista DF
  7. 7arista EF
  8. 8arista BE
6.Difícil
1316411101219ABCDE

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

k = 3
  1. 1arista AB
  2. 2arista AC
  3. 3arista BC
  4. 4arista BD
  5. 5arista CE
  6. 6arista DE
  7. 7arista BE

Soluciones

  1. 1. |E| = 36
  2. 2. |E| = 8
  3. 3. L = 22
  4. 4. L = 14
  5. 5. arista AC
  6. 6. arista BD

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