Ejercicio · ZW-CAMINO-EN-GRAFO-009 · ★★★ Avanzado
Un grafo tiene aristas \(12, 23, 34, 45, 16, 65, 25\). ¿Cuál es la distancia (longitud del camino más corto) entre \(1\) y \(4\)?
Elige una opción.
Ver respuesta
- C. 3
Explicación
Un camino mínimo es 1, 2, 5, 4 (o 1, 6, 5, 4) de longitud 3; ningún camino de longitud 2 existe porque 1 y 4 no tienen vecinos comunes.
Repasa el concepto: Camino en un grafo
Un camino de longitud \(k\) es una sucesión de vértices \(v_0,\dots,v_k\) tal que cada par consecutivo está unido por una arista de \(E\).
\[\{v_{i-1},v_i\}\in E,\qquad i=1,\dots,k\]
Más ejercicios de camino en un grafo
- ZW-CAMINO-EN-GRAFO-001 ¿Cuál es la longitud del camino 1,2,3,4 en un grafo donde 12, 23 y 34 son aristas?
- ZW-CAMINO-EN-GRAFO-002 Un grafo tiene aristas 12, 23, 34, 14, 25. ¿Cuál de estas sucesiones es un camino?
- ZW-CAMINO-EN-GRAFO-003 En el ciclo de 5 vértices 1,2,3,4,5 (aristas 12,23,34,45,51), ¿cuál es la longitud del camino más c…
- ZW-CAMINO-EN-GRAFO-004 Un grafo tiene aristas 12, 13, 23, 34. ¿Cuántos recorridos de longitud 2 (con vértices que pueden r…
- ZW-CAMINO-EN-GRAFO-005 Un camino pasa por 5 vértices distintos. ¿Cuál es su longitud?
- ZW-CAMINO-EN-GRAFO-006 Se tiene el grafo de aristas 12, 23, 34. ¿Cuántos recorridos de longitud 3 van de 1 a 2 (se pueden…
- ZW-CAMINO-EN-GRAFO-007 ¿Cuál es la longitud máxima de un camino sin vértices repetidos en el grafo completo K_6?
- ZW-CAMINO-EN-GRAFO-008 Si hay un camino de u a v en un grafo no dirigido, ¿qué se puede asegurar?