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 , la densité est le rapport :
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 et non , 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, no 1,â , 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).