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 grafo simple tiene 6 vértices con grados 4, 3, 3, 2, 2, 2. ¿Cuántas aristas, |E|, tiene?

deg: 4, 3, 3, 2, 2, 2
|E| =
2.Fácil
AABBCCDDEEFF011000100100100000010011000100000100

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 10 vértices y 18 aristas. ¿Cuántas aristas, k, hay que quitar para obtener un árbol generador?

|V| = 10|E| = 18
k =
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
691518111231614ABCDEF

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

inicio: Ak = 4
  1. 1arista AB
  2. 2arista AC
  3. 3arista BC
  4. 4arista BD
  5. 5arista CE
  6. 6arista DE
  7. 7arista DF
  8. 8arista EF
  9. 9arista BE
6.Difícil
18912320811113ABCDEF

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

|V| = 6|E| = 9
W =

Soluciones

  1. 1. |E| = 8
  2. 2. |E| = 5
  3. 3. k = 9
  4. 4. Circuito euleriano
  5. 5. arista DE
  6. 6. W = 33

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