Fermeture transitive

La clôture transitive, ou fermeture transitive R^trans d'une relation binaire[1] - [2] - [3] R sur un ensemble X est la relation

${\displaystyle 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" ${\displaystyle 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 ${\displaystyle 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[1] R^réfl-trans de R comme la relation

${\displaystyle R^{\text{réfl-trans}}=\bigcup _{n\geq 0}R^{n}=R^{\rm {trans}}\cup \Delta _{X}}$ (Où ${\displaystyle \Delta _{X}}$ est la diagonale de X)

ce qui peut également se traduire ainsi : ${\displaystyle 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 ≤.

La fermeture transitive C(G) du graphe G est construite par ajout d'arcs au graphe G.

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[3] 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 : ${\displaystyle \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.

• Relation d'équivalence engendrée
• Théorie des ensembles
• Opération ensembliste
• Lexique de la théorie des graphes
• Algorithme de Warshall
• Clôture (mathématiques)