Recouvrement (mathématiques)
![Page d’aide sur l’homonymie](http://upload.wikimedia.org/wikipedia/commons/thumb/a/a9/Logo_disambig.svg/20px-Logo_disambig.svg.png)
Pour les articles homonymes, voir Recouvrement.
![](http://upload.wikimedia.org/wikipedia/commons/thumb/1/1f/Racine_carr%C3%A9e_bleue.svg/35px-Racine_carr%C3%A9e_bleue.svg.png)
Cet article est une ébauche concernant les mathématiques.
Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.
Un recouvrement d'un ensemble E est une famille (Xi)i∈I d'ensembles dont l'union contient E, c'est-à-dire telle que tout élément de E appartient à au moins l'un des Xi[1].
Cas particuliers
Certains auteurs[2] imposent de plus que les Xi soient des sous-ensembles de E. Dans ce cas, les Xi forment un recouvrement de E (si et) seulement si leur union est égale à E, et une partition de E s'ils sont de plus non vides et deux à deux disjoints. Par exemple, pour E = {1, 2, 3, 4}, la famille (∅, {1, 2, 3}, {3, 4}) n'est qu'un recouvrement alors que ({1, 2}, {3, 4}) est une partition.
En topologie, un « recouvrement ouvert » d'une partie E d'un espace topologique X est un recouvrement de E par des ouverts Oi de X ou, ce qui revient au même, par des ouverts Oi∩ E de E pour la topologie induite.
Applications
Le recouvrement permet de décrire des problématiques industrielles, telle que la mise en place d'emploi du temps[3] ou la planification routière.
Des problèmes de théorie des graphes, telles que le recouvrement par nœuds, peuvent aussi être décrits par ce paradigme.
Algorithmes de résolution
![](http://upload.wikimedia.org/wikipedia/commons/thumb/8/87/Fairytale_warning.png/17px-Fairytale_warning.png)
Notes et références
- ↑ N. Bourbaki, Éléments de mathématique : Théorie des ensembles [détail des éditions], p. II.27.
- ↑ (en) A. V. Arkhangel'skii, « Covering (of a set) », dans Michiel Hazewinkel, Encyclopædia of Mathematics, Springer, (ISBN 978-1556080104, lire en ligne).
- ↑ (en) K. L. Hoffman et M. Padberg, « Solving airline crew scheduling problems by branch-and-cut », dans Management Science, vol. 39, (ISSN 0025-1909), chap. 6, p. 657-682.
Voir aussi
Articles connexes
- Compacité (mathématiques)
- Lemme de recouvrement de Vitali
Bibliographie
(en) A. Caprara, P. Toth et M. Fischetti, « Algorithms for the set covering problem », dans Annals of Operations Research, vol. 98, Springer, (ISSN 0254-5330, lire en ligne), chap. 1, p. 353-371
Portail des mathématiques