Versione delle 23:51, 22 mar 2014 modifica Luca Ghio (discussione \| contributi) Autoverificati 833 modifiche m →‎Generazione di grafi casuali ← Differenza precedente		Versione attuale delle 17:11, 4 ott 2018 modifica annulla Wim bot (discussione \| contributi) Bot 1 486 modifiche m Bot: Correggo errori comuni (tramite La lista degli errori comuni V 1.1) Etichetta: PAWS [1.2]
Riga 6: * svantaggio: se il grafo non è orientato, la matrice risulta simmetrica rispetto alla diagonale principale; * vantaggio: se il grafo è pesato, il valore di peso si può inserire direttamente nella matrice al posto di 1 → un numero diverso da 0 determina sia l'esistenza dell'arco, sia il valore di peso; * la complessità spaziale è: <math>S \left( n \right) = \Theta \left( {\left\| V \right\|}^2 \right)</math> → vantaggioso per grafi densi; * vantaggio: per verificare una connessione basta accedere ad una cella della matrice → costo unitario. Riga 15: * svantaggio: in un grafo pesato, si deve memorizzare anche il peso sotto forma di denominatore; * svantaggio: gli elementi complessivi nelle liste sono <math>2 \left\| E \right\|</math>; * <math>S \left( n \right) = O \left( \max{\left( \left\| V \right\| , \left\| E \right\| \right)} \right) = O \left( \left\| V \right\| + \left\| E \right\| \right)</math> → è vantaggioso per i grafi sparsi; * svantaggio: l'accesso topologico è meno efficiente perché non ha costo unitario. ==Generazione di grafi casuali== # Il grafo non è modello della realtà, ma viene generato da casuali coppie di vertici → eventuali archi duplicati e cappi da eliminare. # Calcolo probabilistico che nasce da un grafo completo: Tra tutti i possibili <math>\tfrac{V \left( V - 1 \right)}{2}</math> archi del grafo completo, si considerano solo gli archi di probabilità inferiore a un valore soglia di probabilità specificato: :::<math>E=p \frac{V \left( V-1 \right)}{2} \Rightarrow p = 2 \frac{E}{V \left( V-1 \right)} \in \left[ 0,1 \right]</math> ::Vantaggioso perché non si considerano duplicati e cappi, e se vengono richiesti <math>E</math> archi si ottengono in media <math>E</math> archi.

Algoritmi/L'ADT grafo non orientato: differenze tra le versioni