Hypergraphe | EPFL Graph Search

Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?

Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur GraphSearch.

Découvrez-en plus sur les applications Graph.

Les hypergraphes sont des objets mathématiques généralisant la notion de graphe. Ils ont été nommés ainsi par Claude Berge dans les années 1960. Les hypergraphes généralisent la notion de graphe non orienté 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. Un hypergraphe est un couple où est un ensemble non vide (généralement fini) et est une famille de parties non vides de . À l'instar des graphes, on dit que : Les éléments de sont les sommets de . Le nombre de sommets est l'ordre de l'hypergraphe. Les éléments de sont les arêtes de . Les hypergraphes correspondent précisément aux matrices à coefficients 0 ou 1 (dont chaque colonne a au moins un 1). En effet, tout hypergraphe correspond de manière univoque à la matrice telle que : 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 : Le rang d'un hypergraphe est majoré par son ordre. Si , alors 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 . vignette|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, 325, 516).

À propos de ce résultat

Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.

Publications associées (13)

Personnes associées (6)

Concepts associés (49)

Cours associés (6)

Séances de cours associées (69)

Graphe biparti

En théorie des graphes, un graphe est dit biparti si son ensemble de sommets peut être divisé en deux sous-ensembles disjoints et tels que chaque arête ait une extrémité dans et l'autre dans . Un graphe biparti permet notamment de représenter une relation binaire. Il existe plusieurs façons de caractériser un graphe biparti. Par le nombre chromatique Les graphes bipartis sont les graphes dont le nombre chromatique est inférieur ou égal à 2. Par la longueur des cycles Un graphe est biparti si et seulement s'il ne contient pas de cycle impair.

Hypergraphe

Lexique de la théorie des graphes

NOTOC Acyclique graphe ne contenant pas de cycle. Adjacence une liste d'adjacence est une structure de données constituée d'un tableau dont le -ème élément correspond à la liste des voisins du -ème sommet. Adjacence une matrice d'adjacence est une matrice carrée usuellement notée , de dimensions , dont chaque élément est égal au nombre d'arêtes incidentes (ayant pour extrémités) aux sommets d'indices et (pour un graphe simple non pondéré, ). Dans le cas d'un graphe pondéré, chaque élément est égal à la somme du poids des arêtes incidentes.

MATH-448: Statistical analysis of network data

A first course in statistical network analysis and applications.

MATH-506: Topology IV.b - cohomology rings

Singular cohomology is defined by dualizing the singular chain complex for spaces. We will study its basic properties, see how it acquires a multiplicative structure and becomes a graded commutative a

CS-250: Algorithms

The students learn the theory and practice of basic concepts and techniques in algorithms. The course covers mathematical induction, techniques for analyzing algorithms, elementary data structures, ma

Space-Efficient Representations of Graphs

Jakab Tardos

With the increasing prevalence of massive datasets, it becomes important to design algorithmic techniques for dealing with scenarios where the input to be processed does not fit in the memory of a sin

EPFL2022

Spectral Hypergraph Sparsifiers of Nearly Linear Size

Mikhail Kapralov, Jakab Tardos

Graph sparsification has been studied extensively over the past two decades, culminating in spectral sparsifiers of optimal size (up to constant factors). Spectral hypergraph sparsification is a natur

IEEE COMPUTER SOC2022

Cut and spectral sparsification of graphs have numerous applications, including e.g. speeding up algorithms for cuts and Laplacian solvers. These powerful notions have recently been extended to hyperg

ASSOC COMPUTING MACHINERY2021

Configurations tactiques : Rdl Nibble

Explore les configurations tactiques, couvrant la taille minimale des sous-ensembles nécessaires pour couvrir les ensembles d'éléments et le concept de K-sets et de points de base.

Définir les couvertures et les théorèmes d'uniformité

Explore les couvertures fixes et les théorèmes d'uniformité dans les hypergraphes, révélant des aperçus de leurs structures.

L’IA en chimie : Hypergraphe et synthèse rituelle en une seule étape

Explore les applications de l'IA dans la chimie, les hypergraphes, la synthèse rituelle en une seule étape et l'évaluation des modèles rétro-synthétiques.