Una secuencia de vértices conectados describe un desplazamiento por el grafo. Según se repitan aristas o vértices, esa secuencia puede clasificarse como recorrido, trayectoria o camino.
Una arista representa un paso directo entre dos vértices. Al combinar varios pasos obtenemos una secuencia que permite desplazarnos por el grafo.
Estas secuencias son fundamentales para buscar rutas, explorar redes, analizar conectividad y resolver problemas de navegación. Su clasificación depende de qué elementos pueden repetirse.
La traducción de los términos ingleses walk, trail y path varía entre libros. En este curso utilizaremos la siguiente convención:
| Término del curso | Inglés | Repeticiones permitidas |
|---|---|---|
| Recorrido o paseo | Walk | Puede repetir vértices y aristas |
| Trayectoria o sendero | Trail | No repite aristas |
| Camino simple | Path | No repite vértices |
Cuando consultes otra fuente, conviene revisar sus definiciones antes de comparar resultados.
Un recorrido es una secuencia de vértices donde cada par consecutivo está conectado por una arista. Puede pasar varias veces por el mismo vértice o por la misma arista.
En esta secuencia, B se repite y la arista B—C se utiliza en ambos sentidos. Sigue siendo un recorrido válido.
Una trayectoria es un recorrido que no repite aristas. Puede visitar nuevamente un vértice siempre que llegue y salga mediante conexiones diferentes.
El vértice B aparece dos veces, pero ninguna arista se reutiliza. Por eso es una trayectoria, aunque no es un camino simple.
Pulsa un vértice para comenzar y continúa seleccionando nodos adyacentes. La aplicación analizará las repeticiones y clasificará automáticamente la secuencia.
Secuencia
Clasificación
Todo camino es también una trayectoria y un recorrido. Toda trayectoria es un recorrido, pero las implicaciones inversas no siempre se cumplen.
Un camino simple es un recorrido que no repite vértices. Como repetir una arista obligaría a repetir sus extremos, tampoco repite aristas.
Los caminos simples son especialmente importantes porque eliminan vueltas innecesarias y ciclos internos.
La longitud de un recorrido es la cantidad de aristas utilizadas, no la cantidad de vértices escritos.
Un recorrido formado por un único vértice tiene longitud cero y se denomina recorrido trivial.
El primer y el último vértice son los extremos del recorrido. Si ambos coinciden y la longitud es mayor que cero, el recorrido es cerrado.
| Secuencia | Extremos | Tipo |
|---|---|---|
| A → B → C | A y C | Abierto |
| A → B → C → A | A y A | Cerrado |
En un dígrafo, cada paso debe respetar la orientación del arco. La existencia de A→B no permite utilizar B→A salvo que ese arco también exista.
Las definiciones de recorrido, trayectoria y camino se mantienen, pero consideran arcos orientados.
const aristas = [["A", "B"], ["B", "C"], ["C", "D"]];
function sonAdyacentes(a, b) {
return aristas.some(([x, y]) =>
(x === a && y === b) || (x === b && y === a)
);
}
function recorridoValido(secuencia) {
return secuencia.slice(0, -1).every((v, i) =>
sonAdyacentes(v, secuencia[i + 1])
);
}
console.log(recorridoValido(["A", "B", "C", "D"]));function esCaminoSimple(secuencia) {
return new Set(secuencia).size === secuencia.length;
}
function claveArista(a, b) {
return [a, b].sort().join("-");
}
function esTrayectoria(secuencia) {
const usadas = secuencia.slice(0, -1).map((v, i) =>
claveArista(v, secuencia[i + 1])
);
return new Set(usadas).size === usadas.length;
}
console.log(esCaminoSimple(["A", "B", "C"]));
console.log(esTrayectoria(["A", "B", "C", "B"]));Los recorridos describen movimientos posibles a través de un grafo. Restringir la repetición de aristas produce trayectorias, y restringir además la repetición de vértices produce caminos simples.
En el próximo tema estudiaremos ciclos y circuitos, que son recorridos cerrados con propiedades especiales.