Recouvrement (mathématiques)
Pour les articles homonymes, voir Recouvrement.
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 modifier
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 modifier
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 modifier
Notes et références modifier
- 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 modifier
Articles connexes modifier
Bibliographie modifier
(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
