Stavo leggendo su come rappresentare i grafici nella memoria del computer. Ho letto è ideale per rappresentare grafici sparsi per elenchi di adiacenza e grafici densi per matrice di adiacenza. Ma mi piacerebbe capire la differenza principale tra grafici sparsi e densi?Qual è la distinzione tra grafici sparsi e densi?
Il grafico denso è un grafico in cui il numero di bordi è vicino al numero massimo di bordi. Il grafico sparse è un grafico in cui il numero di bordi è vicino al numero minimo di bordi. Il grafico sparse può essere un disconnected graph.
Penso che un grafico con n vertici sia considerato spoglio se ha O (n) o meno spigoli. –
Al contrario, un grafico con n vertici è denso se il numero di fronti è O (n^2) – JayJay
Da here:
Informalmente, un grafico con relativamente poche bordi è scarsa, e un grafico con molti bordi è denso.
Definizione (grafico sparse): un grafico sparse è un grafico G = (V, E) in cui | E | = O (| V |).
Definizione (Grafico denso) Un grafico denso è un grafico G = (V, E) in cui | E | = Θ (| V |).
grafico principale caratteristiche integrali sono il numero di vertici V e numero di archi E. Il rapporto di questi due determina se il grafico è rada o densa (wiki pagina here).
L'intera teoria alla base della scelta della rappresentazione in memoria del grafico riguarda la determinazione del tempo di accesso ottimale rispetto al compromesso dell'impronta di memoria, considerando il dominio dell'oggetto e le specifiche di utilizzo.
Generalmente si desidera avere il tempo di accesso O (1) (e quindi memorizzare il grafico come matrice di adiacenza densa) a meno che non sia possibile tollerare l'impronta di memoria, nel qual caso si sceglie la rappresentazione della matrice sparsa più appropriata (pagina wiki here).
Come i nomi indicano che i grafici sparsi sono scarsamente connessi (es: Alberi). Di solito il numero di fronti è in O (n) dove n è il numero di vertici. Pertanto gli elenchi di adiacenze sono preferiti in quanto richiedono uno spazio costante per ogni spigolo.
I grafici densi sono densamente collegati. Qui il numero di bordi è solitamente O (n^2). Pertanto la matrice di adiacenza è preferita.
Per dare un confronto, supponiamo che il grafico abbia 1000 vertici.
Indipendentemente dal fatto che il grafico sia denso o scarso, la matrice di adiacenza richiede 1000^2 = 1.000.000 di valori da memorizzare.
Se il grafico è collegato in minima parte (ovvero è un albero), l'elenco di adiacenza richiede la memorizzazione di 2.997 valori. Se il grafico è completamente connesso, è necessario memorizzare 3.000.000 di valori.
In matematica, un grafico denso è un grafico in cui il numero di bordi è vicino al numero massimo di bordi. L'opposto, un grafico con pochi spigoli, è un grafico sparso. La distinzione tra grafici sparsi e densi è piuttosto vaga e dipende dal contesto.
Diversi esempi di grafici sparsi sono: Trasporti e reti stradali in cui le intersezioni sono vertici e le strade sono spigoli. Per tali reti, il numero di strade non è significativamente più grande del numero di intersezioni (in altre parole E ~ = c * V, dove c è nell'intervallo di 2-3). Mentre in molti casi i grafici del mondo reale sono sparsi, è possibile creare grafici ponderati che sono molto densi con il peso del bordo che rappresenta una sorta di relazione, ad esempio un peso di bordo grande se due persone hanno visitato lo stesso negozio allo stesso tempo o aveva preso il caffè allo stesso caffè. – harrypotter0
Un altro esempio potrebbe essere quello di prendere un "sotto-grafico" di un grafico sparse che rappresenta una comunità di persone che sono altamente connesse. – harrypotter0
(http://en.wikipedia.org/wiki/Dense_graph) ha informazioni sufficienti – Imposter