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 d'une relation binaire... 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 R de R comme la relation (Où est la diagonale de X) ce qui peut également se traduire ainsi :
C'est donc la clôture réflexive de R, mais aussi la clôture transitive de R. 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 vignette|droite|alt=La fermeture transitive C(G) du graphe G est construite par ajout d'arcs au graphe G.|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 est le graphe C(G) = (V, A). 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 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
Catégorie:Théorie des ensembles Catégorie:Théorie des graphes