Recouvrement (mathématiques)

Un recouvrement d'un ensemble E est une famille (X_i)_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 X_i[1].

Cas particuliers

Certains auteurs[2] imposent de plus que les X_i soient des sous-ensembles de E. Dans ce cas, les X_i 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 O_i de X ou, ce qui revient au même, par des ouverts O_i∩ 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

Notes et références

1. N. Bourbaki, Éléments de mathématique : Théorie des ensembles [détail des éditions], p. II.27.
2. (en) A. V. Arkhangel'skii, « Covering (of a set) », dans Michiel Hazewinkel, Encyclopædia of Mathematics, Springer, 2002 (ISBN 978-1556080104, lire en ligne).
3. (en) K. L. Hoffman et M. Padberg, « Solving airline crew scheduling problems by branch-and-cut », dans Management Science, vol. 39, 1993 (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, 2000 (ISSN 0254-5330, lire en ligne), chap. 1, p. 353-371