Quelle est la distinction entre les graphes clairsemés et denses?
J'ai lu qu'il est idéal de représenter des graphes clairsemés par des listes d'adjacence et des graphes denses par une matrice d'adjacence. Mais je voudrais comprendre la principale différence entre les graphiques clairsemés et denses.
5 réponses
Dense graphe est un graphe dans lequel le nombre d'arêtes est proche du nombre maximum d'arêtes. Éparses graphe est un graphe dans lequel le nombre d'arêtes est proche du nombre minimal d'arêtes. Le graphe clairsemé peut être un graphe déconnecté .
Comme les noms l'indiquent, les graphiques clairsemés sont peu connectés (par exemple: arbres). Généralement, le nombre d'arêtes est en O(n) où n est le nombre de sommets. Par conséquent, les listes de contiguïté sont préférées car elles nécessitent un espace constant pour chaque arête.
Les graphiques denses sont densément connectés. Ici, le nombre d'arêtes est généralement O (N ^ 2). Par conséquent, la matrice de contiguïté est préférée.
Pour donner une comparaison, supposons que graph a 1000 sommets.
Que le graphe soit dense ou non ou clairsemée, la matrice de contiguïté nécessite 1000^2 = 1 000 000 de valeurs à stocker.
Si le graphique est peu connecté (c'est-à-dire qu'il s'agit d'un arbre), la liste d'adjacence nécessite de stocker 2 997 valeurs. Si le graphique est entièrement connecté, il faut stocker 3 000 000 de valeurs.
À Partir de ici:
De manière informelle, un graphe avec relativement peu d'arêtes est clairsemé, et un graphe avec beaucoup d'arêtes est dense.
Définition (graphe clairsemé): un graphe clairsemé est un graphe G = (V, E) dans lequel| E / = O (/V|).
Définition (graphe Dense) un graphe dense est un graphe G = (V, E) dans lequel |E| = Θ (/V|2).
Les principales caractéristiques Intégrales du Graphe sont le nombre de Sommets V et le nombre D'arêtes E. La relation de ces deux détermine si le graphe est clairsemé ou dense (page wiki ici).
Toute la théorie derrière le choix de la représentation graphique en mémoire consiste à déterminer le compromis optimal entre le temps d'accès et l'empreinte mémoire, en tenant compte des spécificités du domaine et de l'utilisation.
Généralement, vous voulez avoir O(1) Temps d'accès (et donc stocker le graphique comme une matrice de contiguïté dense) sauf si vous ne pouvez pas tolérer l'empreinte mémoire, auquel cas vous choisissez la représentation matricielle clairsemée la plus appropriée (page wiki ici).
En mathématiques, un dense graphe est un graphe dans lequel le nombre d'arêtes est proche du nombre maximum d'arêtes. Le contraire, un graphique avec seulement quelques arêtes, est un graphique clairsemé. La distinction entre les graphes clairsemés et denses est plutôt vague et dépend du contexte.