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 grafo simple tiene 5 vértices con grados 3, 3, 2, 1, 1. ¿Cuántas aristas, |E|, tiene?

deg: 3, 3, 2, 1, 1
|E| =
2.Fácil
ABCDE

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

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

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

|V| = 7|E| = 16
k =
4.Media

¿Cuántos circuitos de Hamilton distintos, H, tiene el grafo completo K4? Los circuitos que solo difieren en el vértice inicial o en el sentido cuentan como el mismo.

K4
H =
5.Difícil
5712421564134ABCDEFG

Usa el algoritmo de Dijkstra para hallar la longitud d(F) del camino más corto de A a F en el grafo ponderado.

inicio: Afin: F
d(F) =
6.Difícil
81512521611314ABCDEFG

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 AB
  2. 2arista AC
  3. 3arista BC
  4. 4arista BD
  5. 5arista CE
  6. 6arista DE
  7. 7arista EF
  8. 8arista GB
  9. 9arista GC
  10. 10arista GD

Soluciones

  1. 1. |E| = 5
  2. 2. C
  3. 3. k = 10
  4. 4. H = 3
  5. 5. d(F) = 15
  6. 6. arista GD

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