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 K7?

K7
|E| =
2.Fácil
AABBCCDD0111100010011010

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

|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

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

K4
H =
5.Difícil
182153107191413ABCDEFG

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

inicio: Ck = 4
  1. 1arista AB
  2. 2arista BC
  3. 3arista BD
  4. 4arista CE
  5. 5arista DE
  6. 6arista EF
  7. 7arista GB
  8. 8arista GC
  9. 9arista GD
  10. 10arista GE
6.Difícil
1787201810561215ABCDEFG

Halla el peso total W de un árbol generador mínimo del grafo ponderado.

|V| = 7|E| = 10
W =

Soluciones

  1. 1. |E| = 21
  2. 2. |E| = 4
  3. 3. k = 8
  4. 4. H = 3
  5. 5. arista GB
  6. 6. W = 60

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