Clausura transitiva

La clausura transitiva o cierre transitivo de una relación binaria es la relación binaria más pequeña que siendo transitiva contiene al conjunto de pares de la relación binaria original. La clausura transitiva de una relación R\, se denotada CT(R)\,. En otras palabras, CT(R)\, es la relación binaria que verifica:

  1. R\subseteq CT(R)
  2. CT(R)\, es transitiva
  3. Si R'\, es una relación transitiva tal que R\subseteq R', entonces CT(R)\subseteq R'

Nótese que si R\, es transitiva, entonces CT(R)=R\,. Dada cualquier relación siempre existe su clausura transitiva.

Existencia y descripción

La clausura transitiva de una relación binaria siempre existe, es decir, dada cualquier relación binaria esta puede extenderse hasta que la relación extendida sea transitiva. Además la clausura transitiva que denotaremos aquí mediante \mathcal{R}_{CT} admite una caracterización muy sencilla:

(1)x\mathcal{R}_{CT}y \Rightarrow \quad \exists z_1\dots \exists z_n:
x\mathcal{R}z_1 \land \dots \land z_n\mathcal{R}y

Definiendo las potencias de \mathcal{R} inductivamente:

(2)\begin{matrix} \mathcal{R}^2=\mathcal{R}\times\mathcal{R}
:= \{(x,y)|\exists z:x\mathcal{R}z \land z\mathcal{R}y \} \\
\dots \\ \mathcal{R}^{n+1}= \mathcal{R}\times\mathcal{R}^n \end{matrix}

La clausura transitiva se puede caracterizar como la unión generalizada:

(3)\mathcal{R}_{CT} = \bigcup_{i \in \mathbb{N}} \mathcal{R}^i

Cómo calcularla algorítmicamente

B_\mathcal{R} = [b_{ij}]\quad \land \quad b_{ij} =
\begin{cases} 1 & \mbox{si}\ a_i\mathcal{R}a_j\\
0 & \mbox{si}\ \lnot a_i\mathcal{R}a_j \end{cases}

Una vez calculada se examina en qué caso de los siguientes estamos:

  1. Se encuentran las potencias de B_\mathcal{R} (B_\mathcal{R}^2, B_\mathcal{R}^3,..., B_\mathcal{R}^k, etc.)
  2. Si B_\mathcal{R}^k es la relación total o producto cartesiano, no se buscan más potencias y esa es la Clausura Transitiva.
  3. Si B_\mathcal{R}^k es la matriz nula, entonces la CT(\mathcal{R}) es la unión generalizada (3).
  4. Si B_\mathcal{R}^k es igual a alguna potencia anterior, entonces no se buscan más potencias y la CT(\mathcal{R}) es idéntica que en el punto anterior.

Véase también

This article is issued from Wikipedia - version of the Monday, March 11, 2013. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.