Primi elementi della teoria dei grafi

Grafo ad albero

Un grafo connesso è detto ad albero se non contiene cicli (il nome deriva dalla somiglianza che hanno alcuni di questi grafi con gli alberi). I grafi ad albero hanno un'importante proprietà che li distingue dagli altri grafi:

tutti i vertici sono collegati utilizzando il minor numero possibile di spigoli; se ci sono n vertici gli spigoli sono n-1.

Questo comporta che per ogni coppia di vertici esiste uno e un solo cammino che li ha per estremi.

Il numero degli spigoli che dà luogo al cammino più lungo che unisce due vertici di un grafo ad albero è detto diametro. Il diametro di un grafo ad albero non varia comunque deformiamo la forma del grafo. Ad esempio, il diametro del grafo in figura è 6.

Possiamo attribuire ad ogni vertice di un grafo ad albero un numero detto eccentricità che rappresenta il numero degli spigoli che formano il cammino più lungo tra tutti i cammini che collegano il vertice considerato con tutti gli altri vertici.

Il valore più basso dell'eccentricità è detto raggio del grafo ad albero, ad esempio il raggio del grafo precedente è 3. Con due o con tre vertici c'è un solo modo per unirli e formare un grafo ad albero. Con quattro vertici ci sono due modi differenti per unirli e formare un grafo ad albero; si possono unire i quattro vertici uno di seguito all'altro oppure unire tre vertici a uno stesso vertice, nel primo caso il grafo ha diametro 3 e nel secondo caso il grafo ha diametro 2 pertanto i due grafi non sono isomorfi.

Con 5 vertici ci sono 3 grafi ad albero distinti non isomorfi, con 6 vertici ce ne sono 6, con 7 vertici ce ne sono 11, con 8 vertici ce ne sono 23, con 13 vertici ce ne sono 1301. In un grafo ad albero i vertici che hanno grado 1 sono detti vertici terminali o foglie e un grafo aciclico, non necessariamente connesso, è detto foresta perchè ogni sua componente connessa è un albero.

La struttura ad albero, essendo minimale rispetto al numero degli spigoli, rappresenta la soluzione ideale quando si deve progettare una rete di collegamento (stradale, telefonica, ferroviaria) o un circuito elettrico.