3. Aspects combinatoires
• Intersections
Une partie des problèmes combinatoires est reliée à l'étude des intersections d'ensembles convexes qui sont toujours convexes, comme on l'a vu ci-dessus (l'ensemble vide est, par définition, convexe).
D'après un théorème démontré par Helly, l'intersection C d'une famille de convexes de Rn, telle que l'intersection de toute sous-famille de (n + 1) de ces ensembles soit non vide, est non vide si l'une ou l'autre des hypothèses suivantes est réalisée : la famille est finie ou chacun des convexes de la famille est fermé et borné (c'est-à-dire compact). Ce théorème admet de nombreuses généralisations et applications.
L'étude des propriétés des intersections d'ensembles convexes est facilitée par la notion de graphe d'intersection, qui est utilisée dans des domaines aussi variés que la génétique moléculaire, la psychologie et l'écologie. Pour toute famille d'ensembles, on appelle graphe d'intersection un graphe abstrait où chaque ensemble correspond à un sommet du graphe et où chaque intersection non vide est représentée par un arc réunissant les sommets correspondants ; la figure donne un exemple d'une famille d'ensembles convexes et de leur graphe d'intersection. Tout graphe ayant un nombre fini d'éléments est un graphe d'intersection d'ensembles convexes de R3, mais pas nécessairement un graphe d'intersection d'ensembles convexes de R2 ou de R. Un graphe d'intervalles est un graphe d'intersection d'une famille finie d'ensembles convexes de R (ce sont des intervalles) ; on peut caractériser ces graphes d'intervalles, mais le problème correspondant pour le plan n'est pas résolu.
[…]… pour nos abonnés, l'article se prolonge sur 7 pages…
