Fermeture transitive — Wikipédia
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
[modifier | modifier le code]La clôture transitive, ou fermeture transitive Rtrans d'une relation binaire[1],[2],[3] R sur un ensemble X est la relation
ce qui peut également se traduire ainsi :
Si on nomme la relation "il existe un chemin de taille n entre a et b" On définit
C'est la plus petite relation transitive sur X contenant R.
On définit de même la clôture réflexive transitive[1] Rréfl-trans de R comme la relation
ce qui peut également se traduire ainsi : C'est donc la clôture réflexive de Rtrans, mais aussi la clôture transitive de Rré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
[modifier | modifier le code]![La fermeture transitive C(G) du graphe G est construite par ajout d'arcs au graphe G.](http://upload.wikimedia.org/wikipedia/commons/thumb/1/14/Transitive_closure_neutral.svg/220px-Transitive_closure_neutral.svg.png)
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, Atrans). Les arcs de C(G) sont donc les couples de sommets entre lesquels il existe un chemin dans G. Ceci s'exprime également ainsi :
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
[modifier | modifier le code]- 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)
Références
[modifier | modifier le code]- Jean-Pierre Ramis, André Warusfel et al., Mathématiques Tout-en-un pour la Licence : Niveau L1, Dunod, , 2e éd. (lire en ligne), p. 31.
- Jiří Matoušek et Jaroslav Nešetřil, Introduction aux mathématiques discrètes, Springer, , 453 p. (ISBN 978-2-287-20010-6, lire en ligne), p. 43.
- (en) Eric W. Weisstein, « Transitive closure », sur MathWorld.