La densità di un grafo
La densità di un grafo è una misura che descrive quanto sono connessi i vertici del grafo.
In un grafo non orientato \( G = (V, E) \) con \( n \) vertici e \( E \) archi la densità \( D \) è definita come il rapporto tra il numero effettivo di archi \( E \) e il numero massimo possibile di archi tra \( n \) vertici. La formula è:
\[ D = \frac{2E}{n(n-1)} \]
Per i grafi orientati, invece, la formula della densità \( D \) è leggermente diversa:
\[ D = \frac{E}{n(n-1)} \]
La densità di un grafo varia tra 0 e 1. Una densità di 0 indica un grafo senza archi, mentre una densità di 1 indica un grafo completo.
A cosa serve la densità?
La densità è utilizzata per valutare quanto un grafo è vicino ad essere un grafo completo.
Più alta è la densità, più connesso è il grafo.
E' una misura fondamentale per comprendere la struttura e la connettività di una rete, utile in vari campi come le reti sociali, l'informatica e le scienze naturali. Ad esempio, nelle reti sociali, la densità può indicare quanto è stretta la rete di relazioni. Nelle reti di comunicazione, può aiutare a valutare l'efficienza della rete.
Esempio pratico
Immaginiamo di avere un grafo non orientato con 5 vertici (A, B, C, D, E) e 6 archi.
La densità di questo grafo sarebbe calcolata come segue.
Per prima cosa calcoliamo il numero massimo di archi possibile che il grafo può avere.
$$ \frac{5(5-1)}{2} = 10 $$
Poi applichiamo la formula della densità.
$$ D = \frac{2 \cdot 6}{5(5-1)} = \frac{12}{20} = 0,6 $$
In questo caso, la densità del grafo è 0,6.
In altre parole, il grafo è connesso al 60% del suo potenziale massimo.
La densità di un grafo aumenta in modo lineare con l'aggiunta di archi. Ad esempio, se aggiungi un ulteriore arco al grafo precedente, il numero di archi sale da 6 a 7 e la densità passa da 0.6 a 0.7. In questo caso l'aggiunta di ogni arco incrementa la densità del grafo in modo lineare, aumentando la densità di 0,1 ogni volta. Questo perché la densità è direttamente proporzionale al numero di archi presenti rispetto al numero massimo possibile di archi.
