La clausura de una relación es la relación más pequeña que la contiene y que cumple una propiedad dada. Permite completar relaciones incompletas de manera controlada y mínima.
En muchas situaciones encontramos relaciones que casi cumplen una propiedad pero les falta algún par. Por ejemplo, una relación que debería ser reflexiva pero tiene algunos elementos sin el par (a, a).
La clausura de una relación con respecto a una propiedad es la forma más económica de extenderla para que sí la cumpla: se agregan solo los pares estrictamente necesarios, sin añadir ninguno de más.
Dada una relación R sobre un conjunto A y una propiedad P, la clausura de R respecto de P es la relación R' tal que:
La clausura reflexiva de una relación R sobre A se obtiene agregando todos los pares (a, a) que no estaban en R.
Si R ya es reflexiva, su clausura reflexiva coincide con ella misma.
Ejemplo: Si A = {1, 2, 3} y R = {(1, 2), (2, 3)}, entonces:
Para calcular la clausura reflexiva sumamos todos los pares de la diagonal que aún no existen en la relación.
const A = [1, 2, 3];
const R = [[1, 2], [2, 3]];
function clausuraReflexiva(conjunto, relacion) {
const resultado = [...relacion];
for (const a of conjunto) {
const yaEsta = resultado.some(([x, y]) => x === a && y === a);
if (!yaEsta) resultado.push([a, a]);
}
return resultado;
}
console.log(clausuraReflexiva(A, R));La función agrega solo los pares reflexivos faltantes, preservando los que ya existen.
La clausura simétrica de una relación R se obtiene agregando el par inverso (b, a) por cada par (a, b) que ya está en R.
Ejemplo: Si R = {(1, 2), (2, 3)}, entonces:
Para cada par existente en la relación, verificamos si el par inverso ya está; si no, lo agregamos.
const R = [[1, 2], [2, 3]];
function clausuraSimetrica(relacion) {
const resultado = [...relacion];
for (const [a, b] of relacion) {
const yaEsta = resultado.some(([x, y]) => x === b && y === a);
if (!yaEsta) resultado.push([b, a]);
}
return resultado;
}
console.log(clausuraSimetrica(R));La función recorre cada par y añade su inverso si aún no está presente.
La clausura transitiva es la más compleja. Se obtiene agregando todos los pares que se pueden deducir aplicando la transitividad repetidamente.
Donde R² contiene los pares (a, c) para los que existe b con (a, b) ∈ R y (b, c) ∈ R.
Ejemplo: Si R = {(1, 2), (2, 3)}, la clausura transitiva agrega (1, 3) porque hay un camino 1 → 2 → 3.
El algoritmo de Warshall calcula la clausura transitiva de manera eficiente usando una matriz booleana. Es una de las formas más conocidas de resolver este problema.
El algoritmo recorre todos los posibles intermediarios k y marca que (i, j) pertenece a la clausura si existen los pares (i, k) y (k, j).
function clausuraTransitiva(conjunto, relacion) {
const n = conjunto.length;
const indice = Object.fromEntries(conjunto.map((v, i) => [v, i]));
// Inicializar matriz con los pares de la relación
const M = Array.from({ length: n }, () => Array(n).fill(false));
for (const [a, b] of relacion) {
M[indice[a]][indice[b]] = true;
}
// Algoritmo de Warshall
for (let k = 0; k < n; k++) {
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
if (M[i][k] && M[k][j]) M[i][j] = true;
}
}
}
// Convertir la matriz a pares
const resultado = [];
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
if (M[i][j]) resultado.push([conjunto[i], conjunto[j]]);
}
}
return resultado;
}
const A = [1, 2, 3, 4];
const R = [[1, 2], [2, 3], [3, 4]];
console.log(clausuraTransitiva(A, R));El resultado incluye todos los pares accesibles por caminos de cualquier longitud: (1,2), (1,3), (1,4), (2,3), (2,4), (3,4).
| Clausura | Propiedad que garantiza | Pares que agrega | Complejidad |
|---|---|---|---|
| Reflexiva | Reflexividad | Los pares (a, a) que faltan | O(n) |
| Simétrica | Simetría | Los pares inversos que faltan | O(|R|) |
| Transitiva | Transitividad | Todos los pares alcanzables por caminos | O(n³) con Warshall |
Si se necesita que una relación sea de equivalencia (reflexiva, simétrica y transitiva), se puede construir la clausura aplicando las tres operaciones. El orden importa: primero la reflexiva y la simétrica, luego la transitiva.
Ejemplo: Partiendo de R = {(1, 2)} sobre A = {1, 2, 3}:
El resultado es la relación de equivalencia más pequeña que contiene el par (1, 2). Los elementos 1 y 2 quedan en la misma clase y el elemento 3 forma su propia clase.
La clausura transitiva tiene una interpretación muy práctica en grafos dirigidos: dos nodos a y b están relacionados en la clausura transitiva si y solo si existe un camino de a a b en el grafo.
| Uso en informática | Interpretación de la clausura transitiva |
|---|---|
| Redes y grafos | ¿Existe un camino entre dos nodos? |
| Dependencias de paquetes | ¿A depende transitivamente de B? |
| Jerarquía de clases | ¿Una clase hereda transitivamente de otra? |
| Análisis de código | ¿Una función llama transitivamente a otra? |
| Bases de datos relacionales | Consultas transitivas sobre relaciones jerárquicas |
Las clausuras permiten completar relaciones de manera controlada y mínima para que cumplan propiedades como reflexividad, simetría o transitividad. Son herramientas fundamentales en el análisis de grafos, el diseño de bases de datos y la verificación de propiedades en sistemas.
En el próximo tema estudiaremos la composición de relaciones, una operación que combina dos relaciones para obtener nuevas conexiones entre los elementos de un conjunto.