Cierre Transitivo

El cierre transitivo de una relación es la relación más pequeña que contiene la relación original y satisface la condición de transitividad. En otras palabras, si la relación original tiene conexiones a → b y b → c, entonces el cierre transitivo siempre incluye a → c también.

Definición Formal

Aquí Rⁿ significa la composición n veces de la relación consigo misma. El cierre transitivo así contiene cada conexión que es alcanzable a través de cadenas de longitud finita desde la relación original.

Ejemplo

Sea A = {1,2,3,4}, R = { (1,2), (2,3), (3,4) }.

El cierre transitivo R⁺ = { (1,2), (2,3), (3,4), (1,3), (2,4), (1,4) }, porque (1,3) sigue de (1,2) y (2,3), (2,4) de (2,3) y (3,4), y (1,4) de (1,3) y (3,4) o cadenas más largas.

Propiedades

• El cierre transitivo es siempre transitivo.
• El cierre transitivo contiene la relación original: R ⊆ R⁺.
• El cierre transitivo es la relación transitiva más pequeña que contiene R.
• Si R ya es transitivo, entonces R⁺ = R.

Interpretación Gráfica

En teoría de grafos, el cierre transitivo muestra qué puntos son alcanzables desde un punto dado a través de caminos. Por ejemplo, si hay un camino de A a B y B a C, entonces el cierre transitivo incluye la conexión de A a C.

Resumen

El cierre transitivo es una extensión de una relación que asegura la transitividad, añadiendo los menos nuevos elementos posibles. Este concepto es clave en matemáticas, algoritmos y teoría de grafos.

Ejercicio de Práctica