Hypergraphes

Les hypergraphes sont des objets mathématiques généralisant la notion de graphes. Ils ont été nommés ainsi par Claude Berge en 1960.

Les hypergraphes généralisent la notion de graphe dans le sens où les arêtes ne relient plus un ou deux sommets, mais un nombre quelconque de sommets (compris entre un et le nombre de sommets de l’hypergraphe).

Certains théorèmes de la théorie des graphes se généralisent naturellement aux hypergraphes, par exemple le théorème de Ramsey.

Les hypergraphes sont manipulés dans tous les domaines où on utilise la théorie des graphes : résolution de problèmes de satisfaction de contraintes, traitement d’images, optimisation d’architectures réseaux, modélisation, etc.

Sommaire 1 Définitions 1.1 Hypergraphe 1.2 Hypergraphe uniforme 1.3 Hypergraphe partiel et sous-hypergraphe 1.4 Hypergraphe simple 1.5 Hypergraphe dual 2 Voir aussi 3 Référence

Définitions

Hypergraphe

Un hypergraphe H est un couple (V,E) où V = {v₁,v₂,...,v_n} est un ensemble non vide (généralement fini) et E = E₁,E₂,...,E_m est une famille de parties non vides de V.

A l'instar des graphes, on dit que :

• Les éléments de V sont les sommets de H.
• Le nombre de sommets n est l'ordre de l'hypergraphe.
• Les éléments de E sont les arêtes de H.

Les hypergraphes correspondent précisément aux matrices à coefficients 0 ou 1 (dont chaque colonne a au-moins un 1). En effet, tout hypergraphe H correspond de manière univoque à la matrice telle que :

Hypergraphe uniforme

Parmi les propriétés « nouvelles » — au sens : non définies avec les graphes — introduites avec les hypergraphes figurent deux notions associées.

• On appelle rang d'un hypergraphe le nombre maximum de sommets d'une arête : Le rang d'un hypergraphe est majoré par son ordre. Si rang(H) = 2, alors H est un graphe.
• On appelle anti-rang d'un hypergraphe le nombre minimum de sommets d'une arête :

Par définition d'un hypergraphe, les arêtes sont des parties non vides de l'ensemble des sommets de l'hypergraphe. L'anti-rang d'un hypergraphe est donc non nul.

Un hypergraphe est dit uniforme lorsque son rang et son anti-rang sont égaux.

On parle aussi d' hypergraphe r-uniforme pour désigner un hypergraphe uniforme de rang r.

Hypergraphe partiel et sous-hypergraphe

A l'instar des graphes, on dit que :

• Un hypergraphe partiel H_p = (V,E_p) d'un hypergraphe H = (V,E) est tel que : .

• Un sous-hypergraphe H' = (V',E') d'un hypergraphe H = (V,E) est tel que :
  • et
  • .

Ces notions généralisent à la théorie des hypergraphes les notions de graphe partiel et de sous-graphe.

Hypergraphe simple

A l'instar des graphes, on dit qu'un hypergraphe est simple s'il n'a pas d'arête multiple.

On appelle famille de Sperner (ou clutter en anglais) un hypergraphe simple dont aucune arête n'est contenue dans une autre.

Hypergraphe dual

Soit tel que .

Alors l'hypergraphe défini par H ^* = (E,V ^* ) est appelé hypergraphe dual de H. Il correspond à la transposée de la matrice.

Voir aussi

• Autodual
• Autotransversal
• Transversale

Référence

• Claude Berge, Hypergraphes. Combinatoires des ensembles finis, Gauthier-Villars, 1987. (ISBN 2-04-016906-7).

• Portail des mathématiques