Hypergraphe

Un article de Wikipédia, l'encyclopédie libre.

Vous avez de nouveaux messages (diff^?).

Cet article est une ébauche à compléter concernant les mathématiques, vous pouvez partager vos connaissances en le modifiant.

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

[modifier] Présentation générale

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). De nombreux 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 ont des applications 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’architecture réseaux, modélisation, etc.

[modifier] Définitions

[modifier] Hypergraphe

Soient $V = \left\{ v_1, v_2, \ldots, v_n \right\}$ un ensemble, $E = \left\{ E_1, E_2, \ldots, E_m \right\}$ une famille de parties de $V$ , avec $(m, n) \in \N_*^2$ deux entiers non nuls.

Un hypergraphe $H$ est un couple $(V, E)$ tel que :

$\forall i \in ([1,m]\cap\N) \quad {E_i \neq \varnothing}$
$\bigcup_{i=1}^m E_i \subseteq 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 ou hyper-arêtes de H.

[modifier] 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 :

$\operatorname{rang}(H) = \max_{i \in [1,m]\cap\N} |E_i|$

Le rang d'un hypergraphe est majoré par son ordre. Si rang(H) = 2, alors H est un multigraphe.

On appelle anti-rang d'un hypergraphe le nombre minimum de sommets d'une arête :

$\operatorname{anti-rang}(H) = \min_{i \in [1,m]\cap\N} |E_i|$

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.

[modifier] 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 :

$E_p \subset E$ .

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

$V' \subseteq V$ et

$\forall E_i \in E',\quad E_i \subseteq V' \and E_i \in E$ .

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

[modifier] Hypergraphe simple

A l'instar des graphes, on dit que :

Un hypergraphe simple est un hypergraphe (V, E) tel que, pour toute paire d'hyper-arêtes ${E i, E j}$ de E :

$E_i \subseteq E_j \Rightarrow i = j$ .

Dans le cas où toutes les hyper-arêtes de E sont de cardinalité égale à 2, H est un graphe simple non orienté au sens classique de la théorie des graphes.

[modifier] Hypergraphe dual

Soit $V^* = \left\{ V_j : j = 1, 2, \ldots, |V| \right\}$ tel que $V_j = \left\{ E_i : \left( E_i \in E \right) \wedge \left( v_j \in E_i \right) \right\}$ .