Hypergraphes : théorie des 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.

Les hypergraphes sont des objets très généraux : ce sont des familles de parties. Plusieurs directions ont été explorées en spécifiant certaines propriétés de ces familles de parties (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 matroïdes, avec des illustrations des liens avec la théorie des graphes. Les questions qui suivent peuvent donner quelques pistes :

• Quels sont les différentes caractérisations des matroïdes ?
• Donner des exemples intéressants de matroïdes (que vous avez peut être déjà rencontré sans le savoir)
• 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 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.
• Montrer que la présence de matroïdes sous-jacents à certains problèmes d'optimisation permet d'utiliser des algorithmes gloutons pour les résoudre. Donner des illustrations.

Quelques références (pas exhaustif).

• 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.
• Hypergraphes, livre de C. Berge, Gauthier-Villars (1987). Ce livre a un peu vieilli mais a un intérêt historique.

Retour à la page des sujets.