Recouvrement (mathématiques)

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Page d'aide sur l'homonymie Pour les articles homonymes, voir Recouvrement.

Un recouvrement d'un ensemble X est une famille (Xi)iI de sous-ensembles de X dont l'union est égale à X, c'est-à-dire telle que tout élément de X se trouve dans au moins l'un des Xi.

Cas particuliers[modifier | modifier le code]

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 non vides et deux à deux disjoints.

Exemple[modifier | modifier le code]

Pour l'ensemble {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.

Applications[modifier | modifier le code]

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 nœuds, peuvent aussi être décrits par ce paradigme.

Note et référence[modifier | modifier le code]

  1. (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[modifier | modifier le code]

Articles connexes[modifier | modifier le code]

Bibliographie[modifier | modifier le code]

(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