Fermeture transitive

Fermeture transitive
Page d'aide sur l'homonymie Ne pas confondre avec la clôture transitive.

La fermeture transitive est une opération mathématique pouvant être appliquée sur des ensembles.

Sommaire

Théorie des ensembles

La fermeture transitive d'une relation binaire R sur un ensemble X est la plus petite relation transitive R + sur X contenant R[1]. Si la relation R est transitive, alors on a l'égalité R + = R.
Sinon, la fermeture transitive est définie comme :

R^+=\bigcup_{i\in\N}^{} R^i

Ce qui peut également se traduire ainsi :

\textstyle\forall (a,b) \in X^2,\quad\exists \underset{0\leqslant i\leqslant N}{\{c_i\}} \subset X \quad / \quad a~R^+~b~=~{c_0~R~c_1~R~c_2~R~\ldots~R~c_{N-1}~R~c_N}

Théorie des graphes

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 fermeture transitive C(G) d'un graphe 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.

Articles connexes

Références

  1. ↑ Wolfram Mathworld Transitive closure on Wolfram Mathworld

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Fermeture transitive de Wikipédia en français (auteurs)

Игры ⚽ Поможем сделать НИР

Regardez d'autres dictionnaires:

  • Fermeture (mathématiques) — Clôture (mathématiques) On parle de clôture ou de fermeture en mathématiques dans des contextes très divers. Quelques exemples sont listés ci dessous. Clôture pour des opérations En mathématiques, on dit qu un ensemble est clos pour des fonctions …   Wikipédia en Français

  • Algorithme de Warshall — L algorithme de Warshall permet de construire la fermeture transitive d un graphe orienté ou non orienté. Il doit son nom à Stephen Warshall (en). Sommaire 1 Principe 2 Algorithme …   Wikipédia en Français

  • Algorithme De Warshall — L algorithme de Warshall permet de construire la fermeture transitive d un graphe orienté ou non orienté. Sommaire 1 Principe 2 Algorithme 3 Complexité 4 À voir également …   Wikipédia en Français

  • Algorithme de warshall — L algorithme de Warshall permet de construire la fermeture transitive d un graphe orienté ou non orienté. Sommaire 1 Principe 2 Algorithme 3 Complexité 4 À voir également …   Wikipédia en Français

  • Langage de Dyck — En informatique théorique, et plus spécialement en théorie des langages, les langages de Dyck sont des langages formels particuliers. Un langage de Dyck est l ensemble des mots bien parenthésés, sur un alphabet formé de parenthèses ouvrantes, et… …   Wikipédia en Français

  • Prétopologie — La Prétopologie est une théorie mathématique pour l’analyse, la modélisation et la construction dans les domaines les plus variés : modélisation pour les sciences humaines et sociales, application en théorie des jeux, extension de la notion… …   Wikipédia en Français

  • Relation binaire — En mathématiques, une relation binaire entre deux ensembles E et F (ou simplement relation entre E et F) est caractérisée par un sous ensemble du produit cartésien E × F, soit une collection de couples dont la première composante est dans E et la …   Wikipédia en Français

  • Automate fini — Pour les articles homonymes, voir Automate. Fig. 1 : Automate fini reconnaissant les écritures binaires des multiples de 3. Un automate fini (on dit parfois, par une traduction littér …   Wikipédia en Français

  • Matrice binaire — Définition Une matrice binaire est une matrice dont les coefficients sont soit 0, soit 1. En général ces coefficients sont les nombres de l Algèbre de Boole (logique) dans laquelle on appelle B l ensemble constitué de deux éléments appelés… …   Wikipédia en Français

  • Projet:Mathématiques/Liste des articles de mathématiques — Cette page n est plus mise à jour depuis l arrêt de DumZiBoT. Pour demander sa remise en service, faire une requête sur WP:RBOT Cette page recense les articles relatifs aux mathématiques, qui sont liés aux portails de mathématiques, géométrie ou… …   Wikipédia en Français

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”