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
AABBCCDD0111101011001000

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

|E| =
2.Fácil

Un grafo simple tiene 7 vértices con grados 4, 4, 3, 3, 2, 2, 2. ¿Cuántas aristas, |E|, tiene?

deg: 4, 4, 3, 3, 2, 2, 2
|E| =
3.Media

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

K5
H =
4.Media

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

|V| = 10|E| = 20
k =
5.Difícil
1051181217191514ABCDEFG

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

k = 3
  1. 1arista AB
  2. 2arista BC
  3. 3arista BD
  4. 4arista DE
  5. 5arista DF
  6. 6arista EF
  7. 7arista GB
  8. 8arista GC
  9. 9arista GE
6.Difícil
ABCDE

¿Cuántos recorridos de longitud 2 van de E a D? Un recorrido puede repetir vértices y aristas. Llama al número N.

M = matriz de adyacenciaL = 2
N =

Soluciones

  1. 1. |E| = 4
  2. 2. |E| = 10
  3. 3. H = 12
  4. 4. k = 11
  5. 5. arista AB
  6. 6. N = 1

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