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

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

K5
|E| =
2.Fácil

Un bosque (un grafo sin ciclos) tiene 35 vértices y 2 componentes conexas. ¿Cuántas aristas, |E|, tiene?

|V| = 35c = 2
|E| =
3.Media

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

|V| = 16|E| = 23
k =
4.Media
ABCDECircuito 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| = 5|E| = 6
  1. 1Circuito euleriano
  2. 2Camino euleriano, sin circuito
  3. 3ninguna de las dos
5.Difícil
20112811710652ABCDEFG

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 BD
  4. 4arista CE
  5. 5arista DE
  6. 6arista DF
  7. 7arista EF
  8. 8arista GC
  9. 9arista GD
  10. 10arista GE
6.Difícil
121618111511013517ABCDEFG

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

inicio: Dk = 3
  1. 1arista AB
  2. 2arista BC
  3. 3arista CE
  4. 4arista DE
  5. 5arista DF
  6. 6arista EF
  7. 7arista GB
  8. 8arista GC
  9. 9arista GD
  10. 10arista GE

Soluciones

  1. 1. |E| = 10
  2. 2. |E| = 33
  3. 3. k = 8
  4. 4. Circuito euleriano
  5. 5. arista GC
  6. 6. arista DE

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