Fermeture transitive
Modèle:Ébauche Modèle:Confusion
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 RModèle:Exp d'une relation binaire[1]Modèle:,[2]Modèle:,[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" Modèle:Retrait On définit Modèle:Retrait
C'est la plus petite relation transitive sur X contenant R.
On définit de même la clôture réflexive transitive[1] RModèle:Exp de R comme la relation
ce qui peut également se traduire ainsi : Modèle:Retrait C'est donc la clôture réflexive de RModèle:Exp, mais aussi la clôture transitive de RModèle:Exp. 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[3] est le graphe C(G) = (V, AModèle:Exp). Les arcs de C(G) sont donc les couples de sommets entre lesquels il existe un chemin dans G. Ceci s'exprime également ainsi : Modèle:Retrait
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
- ↑ 1,0 et 1,1 Modèle:Ouvrage.
- ↑ Modèle:Ouvrage.
- ↑ 3,0 et 3,1 Modèle:MathWorld.