Hypergraphe - Définition

Source: Wikipédia sous licence CC-BY-SA 3.0.
La liste des auteurs est disponible ici.

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.

Présentation générale

Les hypergraphes généralisent la notion de graphe dans le sens (SENS (Strategies for Engineered Negligible Senescence) est un projet scientifique qui a pour but...) où les arêtes ne relient plus un ou deux sommets, mais un nombre (La notion de nombre en linguistique est traitée à l’article « 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 (Le terme de graphe désigne en mathématiques une opération d'application. Il possède deux...) se généralisent naturellement aux hypergraphes, par exemple le théorème (Un théorème est une proposition qui peut être mathématiquement démontrée, c'est-à-dire une...) de Ramsey.

Les hypergraphes ont des applications dans tous les domaines où on utilise la théorie (Le mot théorie vient du mot grec theorein, qui signifie « contempler, observer,...) des graphes : résolution de problèmes de satisfaction de contraintes, traitement d’images, optimisation d’architecture réseaux, modélisation, etc.

Définitions

Hypergraphe (Les hypergraphes sont des objets mathématiques généralisant la notion de graphes. Ils ont été...)

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 de H.

un hypergraphe c'est juste une matrice 0-1! mais attention certains mettent les arêtes en ligne (c'est mon cas) et d'autres en colonne... un hypergrahe est autodual si sa matrice est symétrique. le top du top c'est quand un autodual est autotransversal.

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 (Une définition est un discours qui dit ce qu'est une chose ou ce que signifie un nom. D'où la...) 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 (Le mot partiel peut être employé comme :) et sous-hypergraphe

A 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 (Le mot graphe possède plusieurs significations. Il est notamment employé :) partiel et de sous-graphe.

Hypergraphe simple

A l'instar des graphes, on dit que :

  • Un hypergraphe simple est un hypergraphe (V, E) tel que, pour toute paire (On dit qu'un ensemble E est une paire lorsqu'il est formé de deux éléments distincts...) d'arêtes {Ei,Ej} de E :
    E_i \subseteq E_j \Rightarrow i = j.

Dans le cas où toutes les arêtes de E sont de cardinalité (En linguistique, les nombres entiers naturels zéro, un, deux, trois, etc. s'appellent des...) égale à 2, H est un graphe simple non orienté au sens classique de la théorie des graphes.

on les appelle aussi "famille de Sperner" ou "anti-chaîne".

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\}.

Alors l'hypergraphe défini par H * = (E,V * ) est appelé hypergraphe dual de H. beaucoup plus simplement il suffit de prendre la transposée de la matrice.

(12,13,23) est à la fois autodual et autotransversal.

un hypergraphe est "waou!" s'il possède plusieurs propriétés remarquables. ex: P = (123,145,167,246,257,347,356). P est un plan projectif, P est autotransversal, uniforme, régulier et autodual. qui dit mieux?

Page générée en 0.032 seconde(s) - site hébergé chez Contabo
Ce site fait l'objet d'une déclaration à la CNIL sous le numéro de dossier 1037632
A propos - Informations légales | Partenaire: HD-Numérique
Version anglaise | Version allemande | Version espagnole | Version portugaise