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
AABBCCDD0111100010011010

Se muestra la matriz de adyacencia de un grafo simple no dirigido. ¿Cuántas aristas, |E|, tiene el grafo?

|E| =
2.Fácil

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

K11
|E| =
3.Media

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

2 × deg 42 × deg 52 × deg 2
L =
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
149121620157135ABCDEFG

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

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

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) =

Soluciones

  1. 1. |E| = 4
  2. 2. |E| = 55
  3. 3. L = 12
  4. 4. Circuito euleriano
  5. 5. arista EF
  6. 6. d(F) = 15

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