Discussion:Hypergraphe

Hyper-arête, ensemble et notation

Un hypergraphe de rang 2 donne un graphe, pas un multigraphe (E = sous ensemble de l'ensemble des partis de l'ensemble des sommets => au plus une arête reliant 2 sommets). J'ai donc chagé ça.

A part ça bravo Jaymz Height-Field pour les compléments...

Pour un hypergraphe général on peut avoir plusieurs Ei identiques, donc plusieurs arêtes reliant 2 sommets, non ? Jaymz Height-Field 21 mar 2005 à 00:07 (CET)

Ben alors il faut plus utiliser la notation {E_1, E_2,..., E_i} pour désigner l'ensemble des arêtes. Car ce n'est plus un ensemble qu'on considére... Mathématiquement l'ensemble {A,B,C} est égal à l'ensemble {A,C} si B=C... Il faut noter ça comme une collection (avec des parenthéses)... Un ensemble ne contient pas plusieurs fois le même élément... Koko90 21 mar 2005 à 09:43 (CET)

Bonjour,

La notation $\left\{E_{1},E_{2},\ldots ,E_{m}\right\}$ est normalement admise pour une famille de parties(en) $E_{i}$ de $V$, quoique la notation $\left(E_{i}\right)_{i\in \left\{1,2,\ldots ,m\right\}}$ soit la plus fréquente. Toutefois l'ambiguïté est soulignée quant à la formalisation de la possibilité de multiples occurrences dans une famille (indexée ou non). Le plus convenable serait de préciser soit le contexte soit le type d'objet qu'on décrit.

On parle notamment de multi-ensemble(en) pour les collections qui comportent des éléments à occurrence multiple. Contrairement aux familles qui sont plutôt utilisées avec un index (et dont on exploite de fait davantage les propriétés de suite), les multi-ensembles se classent au même rang que les ensembles "classiques". Le "problème" de l'occurrence multiple d'un élément est habituellement réglé par une définition (implicite) de multi-ensemble comme un ensemble de couples (élément-atome, multiplicité) à la différence de celle d'un ensemble qui comporte des éléments-atomes.

Afin de laisser à Koko90 (l'auteur originel) le soin de décider de la notation la plus appropriée, j'annule les modifications que j'avais apportées quant à la notation de famille.

Cordialement --nha de Lyon 28 mai 2006 à 05:24 (CEST)

Avis avant modifications : hyper-arête (le retour), définition et notation

1) Dans la définition, pourquoi l'union des hyperarêtes doit être égale à l'ensemble des sommets ? Même si Claude Berge utilise cette définition il me semble que l'existence de sommets isolés est admise en général. Je note aussi que Berge appelle hypergraphe l'ensemble des parties E lui-même et non le couple (V,E) ce qui ne me semble pas être l'usage aujourd'hui en France. Je serais donc pour enlever cette contrainte dans la définition.

2) Un hypergraphe de rang 2 peut avoir des arêtes avec un seul sommet: ce n'est donc pas un graphe.

Yjp 25 août 2005 à 12:14 (CEST)

Je reviens sur ce que j'ai dit au cas (2) : tels que sont définis les graphes non orientés à cette date sur wikipédia, il est plus juste de dire qu'un hypergraphe de rang 2 n'est pas un graphe non orienté car les arêtes sont une famille et non un ensemble, c'est donc bien un multigraphe. Ce qui est devenu faut dans mon ancienne message est le fait qu'un graphe non orienté peut avoir des arêtes à un seul sommet.

Yjp 7 septembre 2005 à 13:08 (CEST)

Bonjour,

Dans le point (1), je partage complètement la proposition de Yjp sur l'inclusion large $\bigcup _{i=1}^{m}E_{i}\subseteq V$ plutôt que l'exigence d'une couverture totale. Cette condition peut être simplement notée $\bigcup {E}\subseteq V$, où le terme de gauche désigne la réunion de $E$ (sans indice pour l'opérateur de réunion d'ensemble d'ensembles). En outre, étant donné qu'il a été rappelé en préambule que Claude Berge a originellement inspiré ces notions, il ne me paraît pas irrespectueux d'adapter la présentation courante à l'usage contemporain — comme Yjp le suggère.

Dans le commentaire du point (2), il ne me semble pas incorrect d'affirmer qu'un graphe non orienté (au sens de la théorie classique des graphes) peut comporter des arêtes à un seul sommet (en fait : des boucles). Au sens strict, un graphe n'étant pas un multigraphe, ces boucles seraient les seules arêtes des sommets incriminés. A priori un graphe n'est pas nécessairement un graphe simple — c'est-à-dire un graphe sans boucle ni arête multiple — même si, en pratique, on rencontre peu de graphe avec des boucles.

Cordialement --nha de Lyon. 28 mai 2006 à 05:24 (CEST)

Remarques diverses

Bonjour,

Je voudrais évoquer quelques remarques :

Orientation et hypergraphe

La notion d'orientation dans un graphe classique distingue les représentations de paire de sommets (cas du graphe non orienté) ou couple de sommets (cas du graphe orienté) pour une arête donnée. Cette notion se retrouve-t-elle dans le cas des hypergraphes ?

On est intuitivement tenté de répondre par l'affirmative, avec une représentation en partie de sommets (cas d'hypergraphe non orienté) ou tuple de sommets (cas d'hypergraphe orienté).

Boucle et hyper-arête

La notion de boucle dans un graphe définit une arête ayant pour extrémités un seul (et même) sommet. Cette notion se retrouve-t-elle dans le cas des hypergraphes ?

A nouveau, l'intuition ne s'y oppose pas, quoique dans un hypergraphe on parlerait de pseudo-boucle (ou hyper-boucle ?). Autant les sommets (extrémités) d'une arête en boucle dans un graphe sont (tous) identiques, autant un tel cas d'identité totale serait un cas particulier de pseudo-boucle dans un hypergraphe. En effet, il n'y a pas de raison que tous les sommets d'une hyper-arête soient "confondus" dans une pseudo-boucle. Cela revient à considérer une hyper-arête non plus exclusivement comme une partie de sommets, mais potentiellement aussi comme un multi-ensemble de sommets. Cette éventualité est-elle envisagée et envisageable dans la théorie actuelle des hypergraphes ?

Dualité entre hypergraphe et correspondance

Un graphe sert souvent de modèle (plus intuitif) ou de base à la définition d'une relation ou correspondance. Peut-être serait-il pertinent de mentionner la dualité entre les hypergraphes et les correspondances si cette dualité est préservée dans cette théorie.

Merci de votre attention. Bien cordialement --nha de Lyon. 28 mai 2006 à 06:42 (CEST)