La clausura transitiva responde todas las preguntas de alcanzabilidad de un grafo: indica para cada par de vértices si existe algún camino que conecte el primero con el segundo.
Una arista informa una conexión directa, pero muchas aplicaciones necesitan conocer conexiones indirectas. Si A apunta a B y B apunta a C, sabemos que A puede alcanzar a C aunque no exista la arista A → C.
La clausura transitiva reúne toda esa información. Conserva los vértices del grafo y agrega conceptualmente una arista u → v siempre que exista algún camino dirigido desde u hasta v.
La clausura transitiva G⁺ de un grafo dirigido G = (V, E) posee el mismo conjunto de vértices y contiene la arista u → v si v es alcanzable desde u en G.
No se inventan relaciones arbitrarias: cada nueva arista resume un camino que ya existía en el grafo original.
Una relación es transitiva cuando encadenar dos relaciones permite deducir una tercera:
Esta regla puede aplicarse repetidamente. Un camino A → B → C → D permite deducir A → C, B → D y A → D en la clausura.
| Tipo | Condición | Ejemplo |
|---|---|---|
| Directa | Existe una arista u → v | A → B |
| Indirecta | Existe un camino de dos o más aristas | A → B → C |
| Total | Directa o indirecta | Información almacenada en la clausura |
Existen dos convenciones habituales:
En programación suele utilizarse la versión reflexiva porque simplifica la composición de caminos. El laboratorio de este tema sigue esa convención.
La clausura puede almacenarse en una matriz R de V × V:
La fila i responde todos los destinos alcanzables desde i. La columna j muestra todos los orígenes capaces de llegar hasta j.
Avanza paso a paso. En cada etapa se permite utilizar un nuevo vértice como intermediario. Pulsa un nodo para elegir el origen cuyos destinos alcanzables deseas resaltar.
Matriz de alcanzabilidad
Acción actual
Celeste representa un par alcanzable; rosa, un par descubierto en el último paso. En el grafo, verde es el origen seleccionado y celeste señala sus destinos alcanzables según el estado actual de la matriz.
Warshall analiza los vértices uno por uno como posibles intermediarios. Al procesar k pregunta, para cada par i, j:
Si i llega hasta k y k llega hasta j, queda demostrado que i alcanza a j. Las conclusiones se conservan para las etapas siguientes.
function clausuraTransitiva(matrizAdyacencia) {
const n = matrizAdyacencia.length;
const alcance = matrizAdyacencia.map(fila => [...fila]);
// Clausura reflexiva-transitiva
for (let i = 0; i < n; i++) alcance[i][i] = true;
for (let k = 0; k < n; k++) {
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
alcance[i][j] = alcance[i][j] ||
(alcance[i][k] && alcance[k][j]);
}
}
}
return alcance;
}El bucle de k debe ser el exterior. Después de la etapa k, la matriz representa todos los caminos cuyos vértices intermedios pertenecen al conjunto ya procesado.
Cambiar arbitrariamente el orden de los tres bucles puede romper esta interpretación y producir resultados incompletos cuando la actualización se realiza sobre la misma matriz.
Otra posibilidad es ejecutar un recorrido desde cada vértice. Todo nodo visitado desde el origen i se marca como alcanzable en la fila i.
function clausuraConDFS(grafo) {
const vertices = Object.keys(grafo);
const alcance = {};
for (const origen of vertices) {
const visitados = new Set([origen]);
const pila = [origen];
while (pila.length) {
const actual = pila.pop();
for (const vecino of grafo[actual]) {
if (!visitados.has(vecino)) {
visitados.add(vecino);
pila.push(vecino);
}
}
}
alcance[origen] = visitados;
}
return alcance;
}| Método | Tiempo | Espacio del resultado | Conveniente para |
|---|---|---|---|
| Warshall | O(V³) | O(V²) | Grafos densos y representación matricial |
| DFS/BFS desde cada vértice | O(V(V + E)) | O(V²) | Grafos dispersos y listas de adyacencia |
La propia clausura puede contener Θ(V²) pares, incluso cuando el grafo original tiene pocas aristas. Por eso almacenar el resultado completo requiere espacio cuadrático en el peor caso.
Dos vértices u y v pertenecen a la misma componente fuertemente conexa exactamente cuando la matriz indica alcanzabilidad en ambos sentidos.
En la matriz de clausura, una componente fuerte aparece como un bloque cuadrado de unos si agrupamos consecutivamente sus vértices.
La clausura transitiva agrega relaciones implícitas. La reducción transitiva intenta hacer lo contrario: eliminar aristas redundantes sin modificar la alcanzabilidad.
En un DAG, la reducción transitiva es única. En grafos dirigidos con ciclos, el problema requiere más cuidado y puede no tener una única solución.
Una vez construida la matriz, responder “¿v es alcanzable desde u?” cuesta O(1). La inversión inicial es útil cuando se realizarán muchas consultas sobre un grafo que cambia poco.
Si se agregan o eliminan aristas constantemente, recalcular toda la clausura puede ser costoso. Existen algoritmos dinámicos especializados, y la elección depende de la frecuencia de consultas y modificaciones.
La clausura transitiva transforma los caminos de un grafo en respuestas explícitas de alcanzabilidad. Warshall ofrece una solución matricial clara, mientras que los recorridos repetidos aprovechan mejor las representaciones dispersas.
En el próximo tema introduciremos el problema del camino mínimo, donde no solo preguntaremos si un destino es alcanzable, sino cuál es la mejor ruta para llegar hasta él.