Graphe dense

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

En mathématiques, et plus particulièrement en théorie des graphes, un graphe dense (dense graph) est un graphe dans lequel le nombre d'arêtes (ou d'arcs) est proche du nombre maximal. De manière informelle, la densité représente « à quel point tout le monde est lié ».

Le contraire d'un graphe dense, avec un faible nombre d'arêtes (ou d'arcs), est un graphe creux (sparse graph).

La distinction entre graphe creux et dense est plutôt vague et dépend du contexte.

Densité d'un graphe[modifier | modifier le code]

Définition usuelle[modifier | modifier le code]

La densité d'un graphe est définie par le rapport entre le nombre d'arêtes (ou d'arcs) divisé par le nombre d'arêtes (ou d'arcs) possibles.

Dans le cas d'un graphe non orienté simple G = (V, E), la densité est le rapport :

D = \frac{2 \  |E|}{|V| \cdot (|V| - 1)}

Le numérateur compte le nombre d'arêtes existantes et le multiplie par deux, étant donné que chaque arête est liée à une paire de sommets. Le dénominateur dénombre le total d'arêtes nécessaires pour que chaque sommet soit relié à tous les autres (complétude). On calcule n (n-1) et non n^2, car, dans un graphe simple, les arêtes relient deux sommets différents.

La densité 0 correspond au graphe où tous les sommets sont isolés, et la densité 1 au graphe complet[1].

Notion proche[modifier | modifier le code]

Une autre mesure de la densité d'un graphe est l'arboricité qui compte le nombre minimal de forets nécessaires pour couvrir le graphe.

Structures de donnée[modifier | modifier le code]

Les structures de données utilisées pour représenter des graphes peuvent être adaptées à la densité du graphe. En particulier, les graphes denses sont plutôt représentés par des matrices d'adjacence, alors que les graphes creux sont plutôt représentés par des listes d'adjacence.

Références[modifier | modifier le code]

  1. Satu Elisa Schaeffer, Graph clustering, Computer science review 1 (2007), p. 29

Crédit d'auteurs[modifier | modifier le code]