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 :

Quelques références (pas exhaustif).

Retour à la page des sujets.