Hypergraphe

Hypergraphe
Exemple d'hypergraphe : V = {v1,v2,v3,v4,v5,v6,v7}, E = {e1,e2,e3,e4} = {{v1,v2,v3},{v2,v3}, {v3,v5,v6},{v4}}.

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

Définitions

Hypergraphe

Un hypergraphe H est un couple (V,E) où V = {v1,v2,...,vn} est un ensemble non vide (généralement fini) et E = E1,E2,...,Em est une famille de parties non vides de V.

À 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 \mathcal{A}_{n,m}\, telle que :

\forall a_{i,j} \in \mathcal{A}, \quad a_{i,j} = \begin{cases} 1 & \text{si} ~ v_i \in E_j \\ 0 & \text{sinon} \end{cases}

Hypergraphe uniforme

Parmi les propriétés « nouvelles » des hypergraphes par rapport aux graphes 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,\ldots,m\}} |E_i|
    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 :
    \operatorname{anti-rang}(H) = \min_{i \in\{1,\ldots,m\}} |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.

Exemple : l'hypergraphe du plan de Fano

L'hypergraphe du plan de Fano.

L'hypergraphe du plan de Fano a sept sommets appelés points {0,1,2,3,4,5,6} et sept arêtes appelées droites (013, 045, 026, 124, 346, 235, 156). L'ordre (nombre de sommets) est 7.

Le rang et l'anti-rang sont égaux à 3 (nombre de sommets d'une arêtes). Par conséquent, l'hypergraphe du plan de Fano est un hypergraphe 3-uniforme.

Hypergraphe partiel et sous-hypergraphe

À l'instar des graphes, on dit que :

  • Un hypergraphe partiel Hp = (V,Ep) 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.

Hypergraphe simple

À 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 V^* = \{ V_j \mid j = 1, 2, \ldots, |V| \} tel que V_j = \{ E_i \mid ( E_i \in E ) \wedge ( v_j \in E_i ) \}.

Alors l'hypergraphe défini par H * = (E,V * ) est appelé hypergraphe dual de H. Il correspond à la transposée de la matrice. La notion ne coïncide pas avec celle de graphe dual, même dans le cas où l'hypergraphe s'avère être un graphe.

Exemples  :
  • ({1,2},{1,3},{2,3}) est à la fois autodual et autotransversal.
  • ({1,2,3},{1,4,5},{1,6,7},{2,4,6},{2,5,7},{3,4,7},{3,5,6}) est un plan projectif, autotransversal, uniforme, régulier et autodual.

Hypergraphe, recouvrement, partition

L'ensemble des arêtes d'un hypergraphe n'est pas nécessairement un recouvrement, car un sommet peut être de degré nul, c'est-à-dire n'être relié par aucune arête ; dans ce cas, l'union des arêtes ne recouvre pas l'ensemble des sommets. Par exemple, dans l'hypergraphe tel que V = {v1,v2,v3,v4,v5,v6,v7} et E = {e1,e2,e3,e4} = {{v1,v2,v3},{v2,v3},{v3,v5,v6},{v4}}, le sommet v7 est de degré nul ; ne figurant dans aucun des sous-ensembles ei de E, il empêche E d'être un recouvrement. L'ensemble des arêtes d'un hypergraphe n'est un recouvrement que si chaque sommet est au moins de degré 1.

Par suite, il y a partition si l'ensemble des arêtes est un recouvrement et qu'aucun sommet n'est relié par deux arêtes, c'est-à-dire si tout sommet est exactement de degré 1.

Voir aussi

Référence


Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Hypergraphe de Wikipédia en français (auteurs)

Игры ⚽ Поможем сделать НИР

Regardez d'autres dictionnaires:

  • Hypergraphe autodual — Pour les articles homonymes, voir autodual pour les autres notions d autodualité. Un hypergraphe est autodual si sa matrice est symétrique, ex: (12,13,234,235,145). Pour que la matrice soit symétrique il faut l écrire (145,235,234,13,12). Cet… …   Wikipédia en Français

  • Hypergraphes — Hypergraphe Exemple d hypergraphe: V = {v1,v2,v3,v4,v5,v6,v7}, E = {e1,e2,e3,e4} = {{v1,v2,v3},{v2,v3}, {v3,v5,v6},{v4}}. Les hyperg …   Wikipédia en Français

  • Autotransversal — Un hypergraphe autotransversal (self blocking en anglais) est égal à l ensemble de ses transversales minimales. Par exemple, une ensemble de mots est un autotransversal s il a les propriétés suivantes : chaque paire de mots a au moins une… …   Wikipédia en Français

  • Arete transversale — Arête transversale En théorie des hypergraphes, une transversale est une partie qui rencontre toutes les arêtes de l hypergraphe de départ. L ensemble des transversales est la grille. Un ultrafiltre est donc égal à sa grille ! la grille d un …   Wikipédia en Français

  • Arête Transversale — En théorie des hypergraphes, une transversale est une partie qui rencontre toutes les arêtes de l hypergraphe de départ. L ensemble des transversales est la grille. Un ultrafiltre est donc égal à sa grille ! la grille d un autotransversal… …   Wikipédia en Français

  • Arête transversale — En théorie des hypergraphes, une transversale est une partie qui rencontre toutes les arêtes de l hypergraphe de départ. L ensemble des transversales est la grille. Un ultrafiltre est donc égal à sa grille ! la grille d un autotransversal… …   Wikipédia en Français

  • Famille de Sperner — En combinatoire, une famille de Sperner (ou système de Sperner), appelé en l honneur d Emanuel Sperner, est un hypergraphe (E, F) (c est à dire un ensemble E et un ensemble F de parties de E) dans lequel aucun élément de F ne contient un autre.… …   Wikipédia en Français

  • Intersectant — En théorie des graphes, un hypergraphe est dit intersectant si deux quelconques de ses arêtes se rencontrent. Portail des mathématiques Catégorie : Hypergraphe …   Wikipédia en Français

  • Matrice transposée — La matrice transposée (on dit aussi la transposée) d une matrice est la matrice notée (aussi parfois notée , notation recommandée par la norme ISO 31 11, ou ), obtenue en échangeant les lignes et les colonnes de A. Si B = tA alors …   Wikipédia en Français

  • BF-graphe — En théorie des graphes, un BF graphe est un hypergraphe orienté où tous les hyperarcs sont soient des B arcs, soit des F arcs. Un B arc est un hyperarc orienté dont la tête est de taille 1, tandis qu un F arc est un hyperarc orienté dont la queue …   Wikipédia en Français

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”