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
AABBCCDDEEFF011000101010110000000011010100000100

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

|E| =
2.Fácil

Un bosque (un grafo sin ciclos) tiene 38 vértices y 6 componentes conexas. ¿Cuántas aristas, |E|, tiene?

|V| = 38c = 6
|E| =
3.Media
ABCDEFGCircuito 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| = 7|E| = 7
  1. 1Circuito euleriano
  2. 2Camino euleriano, sin circuito
  3. 3ninguna de las dos
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
921512928131412ABCDEFG

El algoritmo de Dijkstra se ejecuta desde A. Haz clic en el vértice que se fija (se hace permanente) en la ronda 6; la propia A es la ronda 1.

inicio: Aronda 6
  1. 1A
  2. 2B
  3. 3C
  4. 4D
  5. 5E
  6. 6F
  7. 7G
6.Difícil
ABCDE

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

M = matriz de adyacenciaL = 3
N =

Soluciones

  1. 1. |E| = 6
  2. 2. |E| = 32
  3. 3. ninguna de las dos
  4. 4. H = 3
  5. 5. G
  6. 6. N = 5

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