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
AABBCCDD0111101011011010

Se muestra la matriz de adyacencia de un grafo simple no dirigido. Halla el grado deg(B) del vértice B.

deg(B) =
2.Fácil

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

K6,4
|E| =
3.Media

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

|V| = 10|E| = 17
k =
4.Media

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

|V| = 11|E| = 22
k =
5.Difícil
1131271892084ABCDEFG

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 DE
  6. 6arista DF
  7. 7arista GB
  8. 8arista GD
  9. 9arista GE
6.Difícil
1598612181721011ABCDEFG

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

inicio: Fk = 2
  1. 1arista AB
  2. 2arista AC
  3. 3arista BD
  4. 4arista CE
  5. 5arista DE
  6. 6arista DF
  7. 7arista EF
  8. 8arista GB
  9. 9arista GD
  10. 10arista GE

Soluciones

  1. 1. deg(B) = 2
  2. 2. |E| = 24
  3. 3. k = 8
  4. 4. k = 12
  5. 5. arista GD
  6. 6. arista CE

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