Fermeture transitive

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Page d'aide sur l'homonymie Ne pas confondre avec la clôture transitive d'un ensemble.

La fermeture transitive est une opération mathématique pouvant être appliquée sur des relations binaires et sur des graphes.

Relation binaire[modifier | modifier le code]

La clôture transitive, ou fermeture transitive Rtrans d'une relation binaire[1],[2] R sur un ensemble X est la relation

R^{trans}=\cup_{n\ge1}R^n,

ce qui peut également se traduire ainsi : \forall (a,b) \in X^2\quad a R^{trans} b\Leftrightarrow\exists n\in\N^*~\exists (c_0,\ldots,c_n)\in X^{n+1}\quad c_0=a,c_n=b\text{ et }c_0Rc_1,c_1 R c_2,\ldots,c_{n-1}Rc_n.

C'est la plus petite relation transitive sur X contenant R.

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.
La fermeture transitive C(G) du graphe G est construite par ajout d'arcs au graphe G.

La clôture transitive, ou fermeture transitive C(G) d'un graphe[2] G est un graphe tel qu'il existe un arc entre toute paire de sommets entre lesquels il existe un chemin. Ceci s'exprime également ainsi :

\textstyle\forall (u,v) \in C(G), \quad u \to v \Leftrightarrow \exists \underset{\underset{u_0=u, u_N=v}{0\leqslant i\leqslant N}}{\{u_i\}} \subset G \quad / \quad { u_0 \to u_1 \to \ldots \to u_{N-1} \to u_N}

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.

Exemple: Si (x,y) est un arc et (y,z) est un arc. La fermeture transitive nous donne donc l'arc (x,z).

Articles connexes[modifier | modifier le code]

Références[modifier | modifier le code]

  1. Jiří Matoušek et Jaroslav Nešetřil (en), Introduction aux Mathématiques Discrètes, Springer, 2004 (ISBN 978-2-28720010-6), p. 43.
  2. a et b (en) Eric W. Weisstein, « Transitive closure », MathWorld.