Los caminos describen cómo desplazarse por un grafo, los ciclos revelan retornos y dependencias circulares, y la conectividad indica si los vértices pueden comunicarse. Estas ideas fundamentan navegación, redes y planificación.
Una vez definido un grafo, las preguntas naturales son: ¿puedo llegar de un vértice a otro?, ¿cuál es la ruta más corta?, ¿hay una vuelta que regresa al origen?, ¿la red está formada por una sola pieza?
Los conceptos de camino, ciclo y conectividad responden a estas preguntas. Aunque nacen en la teoría de grafos, aparecen en ruteo, dependencias de software, redes de comunicación y estructuras de control.
Un recorrido o paseo es una secuencia de vértices consecutivos unidos por aristas. Puede repetir vértices o aristas. Un camino simple es un recorrido que no repite vértices.
En muchos contextos informales se usa «camino» para cualquier recorrido. Al demostrar propiedades conviene especificar si se permite repetir vértices o aristas.
La longitud de un camino sin pesos es la cantidad de aristas que recorre, no la cantidad de vértices.
En un grafo ponderado, una ruta puede tener además un costo que es la suma de los pesos de sus aristas. La longitud por cantidad de aristas y el costo ponderado son medidas diferentes.
En un digrafo, cada paso debe respetar la orientación de la arista. Tener una arista A → B no permite recorrer B → A salvo que exista esa arista inversa.
Esta asimetría es esencial en dependencias, enlaces web y relaciones de seguimiento. La alcanzabilidad debe evaluarse con la dirección correcta.
Un ciclo es un camino cerrado que comienza y termina en el mismo vértice, sin repetir otros vértices en su versión simple. En un grafo no dirigido, un ciclo simple debe tener al menos tres vértices.
Los ciclos pueden ser deseables, como rutas alternativas en una red, o problemáticos, como dependencias circulares entre módulos. El significado depende del dominio.
Si una arista A → B significa «A necesita a B antes de ejecutarse», un ciclo indica una dependencia circular que bloquea el orden de ejecución.
Las herramientas de construcción de software, los gestores de paquetes y los planificadores detectan estos ciclos para informar una configuración imposible o exigir que se elimine una dependencia.
Un grafo dirigido sin ciclos dirigidos se llama DAG, por directed acyclic graph. Los DAG son adecuados para modelar dependencias que siempre avanzan en una dirección.
Un DAG admite al menos un orden topológico: una lista de vértices donde cada arista u → v coloca a u antes que v. Los algoritmos para obtenerlo se estudiarán más adelante.
Un grafo no dirigido es conexo si existe un camino entre cada par de vértices. Si no lo es, sus partes conexas se llaman componentes conexas.
Cada componente conexa es una región máxima del grafo en la que todos los vértices pueden alcanzarse. No hay aristas que conecten una componente con otra.
Decimos que v es alcanzable desde u si existe un camino de u a v. En grafos no dirigidos, la alcanzabilidad es simétrica; en grafos dirigidos no tiene por qué serlo.
La alcanzabilidad se puede calcular explorando vecinos. Los recorridos en profundidad y en anchura son las técnicas básicas para hacerlo.
function hayCamino(adyacentes, origen, destino) {
const pendientes = [origen];
const visitados = new Set([origen]);
while (pendientes.length > 0) {
const actual = pendientes.shift();
if (actual === destino) return true;
for (const vecino of adyacentes.get(actual) ?? []) {
if (!visitados.has(vecino)) {
visitados.add(vecino);
pendientes.push(vecino);
}
}
}
return false;
}
const red = new Map([
["A", new Set(["B", "C"])],
["B", new Set(["D"])],
["C", new Set()],
["D", new Set()]
]);
console.log(hayCamino(red, "A", "D")); // true
console.log(hayCamino(red, "C", "D")); // falseEl conjunto visitados evita recorrer una y otra vez los mismos vértices y permite que el algoritmo termine incluso si hay ciclos. El uso de una cola produce una exploración en anchura.
Para hallar todas las componentes de un grafo no dirigido, se inicia una exploración desde un vértice no visitado. Todos los vértices alcanzados forman una componente; luego se repite desde otro vértice pendiente.
La cantidad de exploraciones iniciadas es exactamente la cantidad de componentes. Esta técnica también ayuda a detectar islas de red o grupos separados de datos.
function componentesConexas(adyacentes) {
const visitados = new Set();
const componentes = [];
for (const inicio of adyacentes.keys()) {
if (visitados.has(inicio)) continue;
const componente = [];
const pendientes = [inicio];
visitados.add(inicio);
while (pendientes.length > 0) {
const actual = pendientes.pop();
componente.push(actual);
for (const vecino of adyacentes.get(actual) ?? []) {
if (!visitados.has(vecino)) {
visitados.add(vecino);
pendientes.push(vecino);
}
}
}
componentes.push(componente);
}
return componentes;
}La implementación usa una pila, por lo que explora en profundidad. En un grafo no dirigido, la lista de adyacencia debe contener ambos sentidos de cada arista y una clave para cada vértice aislado para que las componentes se calculen correctamente.
Un digrafo es fuertemente conexo si para cualquier par u y v hay un camino de u a v y otro de v a u. Es débilmente conexo si al ignorar las direcciones, el grafo resultante es conexo.
La conectividad fuerte representa comunicación bidireccional posible mediante rutas, aunque no exista una arista directa en ambos sentidos.
En un grafo no ponderado, la distancia d(u, v) es la longitud del camino más corto entre u y v. Si no existe camino, la distancia se considera infinita o no definida según la convención.
En grafos ponderados, la ruta con menos aristas puede no ser la de menor costo. Allí se requieren algoritmos que tomen en cuenta los pesos.
En un grafo conexo, la excentricidad de un vértice es su máxima distancia a otro vértice. El radio es la menor excentricidad y el diámetro es la mayor.
Un vértice cuya excentricidad alcanza el radio se llama centro del grafo. Esta noción ayuda a elegir ubicaciones relativamente cercanas a todos los puntos de una red.
Una arista puente es una arista cuya eliminación aumenta el número de componentes conexas. Un vértice de articulación tiene el mismo efecto al eliminarse junto con sus aristas incidentes.
Estas estructuras señalan puntos vulnerables de una red: una falla en un puente o articulación puede aislar una región completa.
Un camino euleriano recorre cada arista exactamente una vez. Un ciclo euleriano además termina en el vértice donde comenzó.
La condición se refiere a aristas, no a vértices. Las rutas de reparto, la inspección de conexiones y algunos problemas de trazado se relacionan con recorridos eulerianos.
Un camino hamiltoniano visita cada vértice exactamente una vez. Un ciclo hamiltoniano también vuelve al origen después de visitar todos los vértices.
No existe una condición simple y general tan directa como la de Euler para reconocer ciclos hamiltonianos. Problemas relacionados con visitar todas las ciudades son difíciles y aparecen en optimización de rutas.
Un árbol es una forma mínima de mantener conectados n vértices: usa exactamente n - 1 aristas. Si se elimina cualquier arista, deja de estar conectado; si se agrega una, aparece un ciclo.
Esta tensión entre costo y redundancia aparece al diseñar redes. Un árbol reduce conexiones, mientras que los ciclos mejoran la tolerancia a fallos.
El mismo grafo puede responder preguntas diferentes según se estudien caminos, costos, ciclos o componentes. Elegir la propiedad correcta evita aplicar un algoritmo de navegación a un problema de dependencias, o viceversa.
Camino, ciclo y conectividad convierten una lista de conexiones en propiedades útiles para resolver problemas. En el próximo tema estudiaremos algoritmos sobre grafos que automatizan estas exploraciones y optimizaciones.