title: Fermeture transitive
text: # 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.
  
  