AccueilđŸ‡«đŸ‡·Chercher

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

  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, no 1,‎ , p. 27 - 39

Crédit d'auteurs

Article connexe

Cet article est issu de wikipedia. Text licence: CC BY-SA 4.0, Des conditions supplĂ©mentaires peuvent s’appliquer aux fichiers multimĂ©dias.