Fermeture transitive

Cet article est une ébauche concernant les mathématiques.

Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.

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^[1]^,^[2]^,^[3] 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^[1] 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}

(Où

\Delta _{X}

est la diagonale de 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

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 : $\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.

Articles connexes

Références

↑ ^{a et b} Jean-Pierre Ramis, André Warusfel et al., Mathématiques Tout-en-un pour la Licence : Niveau L1, Dunod, 2013, 2^e éd. (lire en ligne), p. 31.
↑ Jiří Matoušek et Jaroslav Nešetřil, Introduction aux mathématiques discrètes, Springer, 2004, 453 p. (ISBN 978-2-287-20010-6, lire en ligne), p. 43.
↑ ^{a et b} (en) Eric W. Weisstein, « Transitive closure », sur MathWorld.

Portail des mathématiques

[ToutEnUn-1] {a et b} Jean-Pierre Ramis, André Warusfel et al., Mathématiques Tout-en-un pour la Licence : Niveau L1, Dunod, 2013, 2^e éd. (lire en ligne), p. 31.

[2] Jiří Matoušek et Jaroslav Nešetřil, Introduction aux mathématiques discrètes, Springer, 2004, 453 p. (ISBN 978-2-287-20010-6, lire en ligne), p. 43.

[wolfram-3] {a et b} (en) Eric W. Weisstein, « Transitive closure », sur MathWorld.

[1]

[2]

[3]