Primi elementi della teoria dei grafi

Formula di Cayley

Il matematico e chimico Artur Cayley studiò e introdusse i grafi ad albero per capire perchè alcuni idrocarburi saturi pur avendo la stessa massa molecolare e la stessa composizione percentuale di atomi di carbonio e di idrogeno presentavano proprietà fisiche diverse ma reattività chimiche quasi simili. Ad esempio, ci sono tre differenti idrocarburi saturi che hanno la stessa formula bruta C₅H₁₂ ma una diversa densità, un diverso punto di ebollizione e un diverso punto di fusione. Cayley ipotizzò che questi tre idrocarburi avessero una diversa struttura spaziale molecolare e per rappresentare questa diversità utilizzò un grafo ad albero dove i vertici erano gli atomi di carbonio e di idrogeno e gli spigoli i legami tra carbonio e idrogeno e tra carbonio e carbonio tenendo presente che il carbonio ha valenza quattro, cioè ha quattro legami chimici e l'idrogeno ha valenza uno, cioè un solo legame chimico.

E' proprio questa diversa disposizione degli atomi nella molecola che determina le differenti proprietà fisiche. Incoraggiato da questo risultato Cayley si pose il problema: quanti diversi alberi si possono formare con n vertici etichettati? Un vertice è detto etichettato se è identificato da una lettera o da un numero o da un colore. Non ò difficile verificare che con due vertici c'è un solo albero etichettato, mentre con tre vertici ci sono tre alberi etichettati.

Attenzione a non confondere il grafo ad albero con tre vertici non etichettati con quello con tre vertici etichettati. C'ò un solo albero con tre vertici non etichettati perchè i vertici non sono distinguibili. Con quattro vertici ci sono 16 alberi etichettati.

La formula di Cayley afferma: il numero T_n di alberi etichettati distinti con n vertici è n^n-2.

T_n = n^n-2

Con cinque vertici etichettati ci sono quindi

5^5-2 = 5³ = 125

alberi distinti.