- Recouvrement (mathématiques)
-
Pour les articles homonymes, voir Recouvrement.Un recouvrement d'un ensemble X est un ensemble P de sous-ensembles non vides de X tel que l'union de ces sous-ensembles soit égale à X. Autrement dit, P est un recouvrement de X si et seulement si tout élément x de X se trouve dans au moins l'un des éléments de P.
Sommaire
Cas particuliers
En topologie, un recouvrement ouvert d'un espace topologique (X,T) est un recouvrement de l'ensemble X par des ouverts de la topologie T. Une partition est un recouvrement particulier où les sous-ensembles sont deux à deux disjoints.
Exemple
Soit l'ensemble X suivant : X = {1,2,3,4}. Un recouvrement de X est {{1,2,3},{3,4}}. Une partition de X est {{1,2},{3,4}}.
Applications
Le recouvrement permet de décrire des problématiques industrielles, telle que la mise en place d'emploi du temps[1] ou la planification routière.
Des problèmes de théorie des graphes, telles que le recouvrement par noeuds, peuvent aussi être décrits par ce paradigme.
Algorithmes de résolution
Notes et références
- (en) K. L. Hoffman et M. Padberg, « Solving airline crew scheduling problems by branch-and-cut », vol. 39 : Management Science, JSTOR, 1993, p. 657-682
Bibliographie
(en) A. Caprara, P. Toth, et M. Fischetti, « Algorithms for the set covering problem », vol. 98 : Annals of Operations Research, Springer, 2000 [lire en ligne], p. 353-371
Catégories :- Système d'ensembles
- Théorie des ensembles
Wikimedia Foundation. 2010.
