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 16 vértices y 4 componentes conexas. ¿Cuántas aristas, |E|, tiene?

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

Un árbol tiene 11 vértices. ¿Cuántas aristas, |E|, tiene?

|V| = 11
|E| =
3.Media

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

|V| = 9|E| = 20
k =
4.Media

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

3 × deg 33 × deg 44 × deg 5
L =
5.Difícil
316104151211119ABCDEFG

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

inicio: Gk = 4
  1. 1arista AB
  2. 2arista AC
  3. 3arista BC
  4. 4arista BD
  5. 5arista CE
  6. 6arista DE
  7. 7arista DF
  8. 8arista GD
  9. 9arista GE
6.Difícil
ABCDE

¿Cuántos recorridos cerrados de longitud 2 empiezan y terminan en E? Un recorrido puede repetir vértices y aristas. Llama al número N.

M = matriz de adyacenciaL = 2
N =

Soluciones

  1. 1. |E| = 12
  2. 2. |E| = 10
  3. 3. k = 12
  4. 4. L = 23
  5. 5. arista BC
  6. 6. N = 3

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