Fermeture transitive
# Fermeture transitive

La fermeture transitive est une opération mathématique pouvant être appliquée sur des relations binaires sur un ensemble, autrement dit sur des graphes orientés.

## Relation binaire

La clôture transitive, ou fermeture transitive $R^{trans}$ d'une relation $binaire^,^,$ R sur un ensemble X est la relation

$R^{\rm {trans}}=\bigcup _{n\geq 1}R^{n},$

ce qui peut également se traduire ainsi :

Si on nomme la relation "il existe un chemin de taille n entre a et b" $P_{n}(a,b):\Leftrightarrow \exists (c_{0},\ldots ,c_{n})\in X^{n+1}\quad c_{0}=a,c_{n}=b{\text{ et }}c_{0}Rc_{1},c_{1}Rc_{2},\ldots ,c_{n-1}Rc_{n}$ On définit $aR^{\rm {trans}}b:\Leftrightarrow \exists n\in \mathbb {N} ^{*}\quad P_{n}(a,b).$

C'est la plus petite relation transitive sur X contenant R.

On définit de même la clôture réflexive transitive $R^{réfl-trans}$ de R comme la relation

$R^{\text{réfl-trans}}=\bigcup _{n\geq 0}R^{n}=R^{\rm {trans}}\cup \Delta _{X}$

$\Delta _{X}$

ce qui peut également se traduire ainsi : $aR^{\text{réfl-trans}}b:\Leftrightarrow \exists n\in \mathbb {N} \quad P_{n}(a,b)\Leftrightarrow (aR^{\rm {trans}}b{\text{ ou }}a=b).$ C'est donc la clôture réflexive de $R^{trans},$ mais aussi la clôture transitive de $R^{réfl}.$ C'est la plus petite relation réflexive et transitive sur X contenant R.

Par exemple sur l'ensemble Z des entiers relatifs, la clôture transitive de la relation strictement acyclique R définie par x R y ⇔ y = x + 1 est l'ordre strict usuel <, et la clôture réflexive transitive de R est l'ordre usuel ≤.

## Théorie des graphes

Un graphe orienté G = (V, A) est une relation binaire A sur l'ensemble V de ses sommets. Sa clôture transitive, ou fermeture transitive est le graphe C(G) = (V, $A^{trans}).$ Les arcs de C(G) sont donc les couples de sommets entre lesquels il existe un chemin dans G. Ceci s'exprime également ainsi : $\forall (a,b)\in V^{2}\quad a\to b{\text{ dans }}C(G)\Leftrightarrow \exists n\in \mathbb {N} ^{*}~\exists (c_{0},\ldots ,c_{n})\in V^{n+1}\quad c_{0}=a,c_{n}=b{\text{ et }}c_{0}\to c_{1}\to \ldots \to c_{n-1}\to c_{n}{\text{ dans }}G.$

La fermeture transitive peut se calculer au moyen de matrice binaire. On privilégie souvent la notation B = {1, 0}. Quand on programme des algorithmes utilisant ces matrices, la notation {VRAI, FAUX} peut coexister avec la notation {1, 0} car de nombreux langages acceptent ce polymorphisme.

