Estaba leyendo formas de representar gráficas en la memoria de la computadora. Leí que es ideal para representar gráficos dispersos por listas de adyacencia y gráficos densos por matriz de adyacencia. Pero me gustaría entender la diferencia principal entre gráficos dispersos y densos.¿Cuál es la distinción entre gráficos dispersos y densos?
El gráfico denso es un gráfico en el que el número de aristas es similar al número máximo de aristas. Gráfico disperso es un gráfico en el que el número de aristas se acerca al número mínimo de aristas. El gráfico disperso puede ser disconnected graph.
Creo que un gráfico con n vértices se considera escaso si tiene O (n) o menos aristas. –
Por el contrario, un gráfico con n vértices es denso si el número de bordes es O (n^2) – JayJay
De here:
De manera informal, un gráfico con relativamente pocos bordes es escasa, y un gráfico con muchas aristas es densa.
Definición (Gráfico disperso): Un gráfico disperso es un gráfico G = (V, E) en el que | E | = O (| V |).
Definición (gráfico denso) Un gráfico denso es un gráfico G = (V, E) en el que | E | = Θ (| V |).
principales características integrales gráfico son número de vértices V y el número de bordes E. La relación de estos dos determina si el gráfico es escasa o denso (página wiki here).
La teoría detrás de la elección de la representación gráfica en memoria consiste en determinar el tiempo de acceso óptimo frente a la compensación de la huella de memoria, teniendo en cuenta el dominio del sujeto y los detalles de uso.
Generalmente, desea tener O (1) tiempo de acceso (y así almacenar el gráfico como una matriz de adyacencia densa) a menos que no pueda tolerar la huella de memoria, en cuyo caso elige la representación de matriz dispersa más apropiada (página wiki here).
Como los nombres indican que los gráficos dispersos están escasamente conectados (por ejemplo, Árboles). Usualmente el número de bordes está en O (n) donde n es el número de vértices. Por lo tanto, se prefieren las listas de adyacencia ya que requieren espacio constante para cada borde.
Los gráficos densos están densamente conectados. Aquí el número de aristas es generalmente O (n^2). Por lo tanto, se prefiere la matriz de adyacencia.
Para dar una comparación, supongamos que el gráfico tiene 1000 vértices.
Independientemente de si el gráfico es denso o escaso, la matriz de adyacencia requiere 1000^2 = 1,000,000 de valores para almacenarse.
Si el gráfico está mínimamente conectado (es decir, es un árbol), la lista de adyacencias requiere almacenar 2.997 valores. Si el gráfico está completamente conectado, se requiere almacenar 3,000,000 de valores.
En matemáticas, un gráfico denso es un gráfico en el que el número de aristas se acerca al número máximo de aristas. Lo contrario, un gráfico con solo unos pocos bordes, es un gráfico disperso. La distinción entre gráficos dispersos y densos es bastante vaga y depende del contexto.
Varios ejemplos de gráficos dispersos son: Transporte y redes de carreteras donde las intersecciones son vértices y las carreteras son bordes. Para tales redes, el número de carreteras no es significativamente mayor que el número de intersecciones (en otras palabras E ~ = c * V, donde c está en el rango de 2-3). Si bien en muchos casos los gráficos del mundo real son escasos, es posible crear gráficos ponderados que son muy densos y el peso del borde representa algún tipo de relación, como un gran peso de borde si dos personas visitaron la misma tienda al mismo tiempo o tomé un café en la misma cafetería. – harrypotter0
Otro ejemplo podría ser tomar un "sub-gráfico" de un gráfico disperso que representa una comunidad de personas que están altamente conectadas. – harrypotter0
(http://en.wikipedia.org/wiki/Dense_graph) tiene información suficiente – Imposter