Densité d'un graphe

En mathématiques, et plus particulièrement en théorie des graphes, on peut associer à tout graphe un entier appelé densité du graphe. Ce paramètre mesure si le graphe a beaucoup d'arêtes ou peu. Un graphe dense (dense graph) est un graphe dans lequel le nombre d'arêtes (ou d'arcs) est proche du nombre maximal, par exemple un nombre quadratique par rapport au nombre de sommets. Un graphe creux (sparse graph) a au contraire peu d'arêtes, par exemple un nombre linéaire. La distinction entre graphe creux et dense est plutôt vague et dépend du contexte.

Densité d'un graphe

Définition usuelle

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

Une mesure de la densité d'un graphe est l'arboricité qui compte le nombre minimal de forets nécessaires pour couvrir le graphe. On peut aussi utiliser la dégénérescence.

Aspects combinatoires

La notion de densité apparaît en combinatoire, notamment dans le lemme de régularité de Szemerédi.

Aspects algorithmiques

Structures de données

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 mieux représentés par des listes d'adjacence.

Complexité dépendant de la densité

Certains algorithme sont construits pour être efficaces sur les graphes d'une certaine densité, et sont plutôt mauvais si on les utilise sur des graphes quelconques. On parle typiquement d'algorithmes pour les graphes denses ou pour les graphe creux.

Problème du graphe le plus dense

Il existe plusieurs problèmes algorithmiques appelés « problème du graphe le plus dense » (densest subgraph). L'un d'eux est le problème du k-sous-graphe le plus dense, dans lequel, pour un graphe donné, on cherche le sous-graphe sur k sommets étant le plus dense. C'est un problème NP-complet, même restreint aux graphes bipartis et aux graphes cordaux^[2].

Références

↑ Satu Elisa Schaeffer, Graph clustering, Computer science review 1 (2007), p. 29
↑ D.G. Corneil et Y. Perl, « Clustering and domination in perfect graphs », Discrete Applied Mathematics, vol. 9, n^o 1,‎ 1984, p. 27 - 39

Crédit d'auteurs

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Dense graph » (voir la liste des auteurs).

Article connexe

Pseudo-forêt

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

[2] D.G. Corneil et Y. Perl, « Clustering and domination in perfect graphs », Discrete Applied Mathematics, vol. 9, n^o 1,‎ 1984, p. 27 - 39

[1]

[2]