Hypergraphes et matroïdes.
Les hypergraphes généralisent la notion de graphe en
définissant sur un ensemble fixé V des hyperarêtes qui contiennent
autant de sommets que l'on veut, contrairement aux arêtes
classiques qui ne joignent que deux sommets. Un livre de
référence est celui de Berge intitulé
"Hypergraphes". Les premières définitions sont
données au début de son chapître 1. Du point de
vue, théorique les hypergraphes permettent de
généraliser certains théorèmes de graphes,
voire de factoriser plusieurs théorèmes de graphes en un
seul théorème d'hypergraphes. Du point de vue pratique,
ils sont parfois préférés aux graphes car
modélisant mieux certains types de contraintes.
Il faut noter que dans certains cas, l'étude des hypergraphes se
résume à l'étude de famille de parties ayant
certaines propriétés (parfois sans
référence directe à des problèmes de
graphes). Plutôt que de parler d'hypergraphes, les auteurs
préférent alors mentionner les théories plus
spécifiques correspondant aux propriétés
étudiées, par exemple : la théorie de Sperner
(étude des familles de parties par rapport à la relation
d'inclusion) ou la théorie des Matroïdes (étude des
familles de parties closes pour la notion de sous-partie et pouvant se
"compléter" les unes les autres).
L'objectif ici est de donner un survol de la théorie des
hypergraphes, illustrant les liens avec la théorie des graphes
et illustrant les types de résultats associés à
des théories plus spécifiques comme la théorie de
Sperner ou la théorie des Matroïdes. Les questions qui
suivent peuvent donner quelques pistes :
- Un hypergraphe simple
est un hypergraphe qui ne contient pas deux hyperarêtes telles
que l'une est include dans l'autre. Etant donné V avec n sommets, quel est le nombre
maximum d'hyperarêtes d'un hypergraphe simple sur V ? (La
solution à cette question est souvent considérée
comme le premier théorème de la théorie de
Sperner).
- Les hypergraphes, et en particulier les matroïdes,
permettent de généraliser et parfois factoriser des
théorèmes classiques de graphes. Trouver des
illustrations. Par exemple, présenter les matroïdes et un
théorème comme le théorème d'intersection
de matroïdes de Edmonds. Ce théorème redonne en
corollaire le théorème de König-Egervary qui relie
couplage maximum et couverture minimum par des sommets dans les graphes
bipartis. Il redonne
comme autre corollaire un cas particulier de théorème de
Gallai-Milgram : pour toute orientation acyclique d'un graphe G, les
sommets peuvent être couverts par ≤ alpha(G) chemins disjoints,
où alpha(G) est le
cardinal maximum d'un indépendant de G.
- Derrière ce pouvoir de généralisations
mathématiques, montrer que les problèmes d'optimisation
sont susceptibles d'avoir une plus forte complexité dans leur
version hypergraphe que dans
leur version graphe. Par
exemple, qu'en est-il de la 2-coloration ?
Quelques références (pas
exhaustif).
- Hypergraphes, livre de
C. Berge, Gauthier-Villars (1987).
- Combinatorics of finite sets,
livre de I. Anderson, Oxford
University Press (1989). Un livre sur la théorie de
Sperner.
- Introduction to Graph Theory,
livre de D. West, Prentice Hall
(2001). La section 8.2 est une bonne introduction aux
matroïdes, avec en particulier une preuve du
théorème d'intersection de matroïdes de Edmonds.
L'application du théorème de Edmonds au cas particulier
du théorème de Gallai-Milgram correspond à
l'exercice 8.2.50.
Retour à la page des sujets.