Formula di Cayley

La formula di Cayley è usata in matematica nella teoria dei grafi.

Lista completa degli alberi etichettati con 2, 3 e 4 vertici.

Essa afferma che il numero di alberi ricoprenti che si possono costruire su un grafo con n vertici etichettati (con n > 1), è pari a n n-2.

Si parla di vertici "etichettati" quando sono identificati tramite numeri, colori, ecc. Gli alberi con vertici etichettati sono chiamati a volte alberi di Cayley.

Per esempio, per alberi con 2, 3 e 4 vertici la formula fornisce i seguenti risultati:

  •   (1 albero con 2 vertici)
  •   (3 alberi con 3 vertici)
  •   (16 alberi con 4 vertici)

StoriaModifica

Questa formula fu scoperta dal tedesco Carl Borchardt nel 1860, che la dimostrò tramite un determinante.[1]
Nel 1889 l'inglese Arthur Cayley estese la formula, tenendo conto anche del grado (cioè della molteplicità) dei vertici. Cayley riconobbe a Borchardt la paternità della formula originale, ma in seguito il nome « formula di Cayley » è entrato nell'uso.[2]

DimostrazioniModifica

Esistono diverse dimostrazioni della formula di Cayley. Un esempio classico utilizza il teorema di Kirchhoff, applicabile ad un grafo qualunque, mentre la formula di Cayley si limita ai grafi completi.

 Lo stesso argomento in dettaglio: Teorema di Kirchhoff.

Nel 1918 Heinz Prüfer ne diede una dimostrazione tramite il codice di Prüfer, che fornisce una descrizione compatta e univoca albero con n vertici etichettati tramite una sequenza del tipo

 

Ad ogni sequenza P corrisponde uno ed un solo albero con n vertici etichettati.

NoteModifica

  1. ^ Borchardt C.W., Über eine Interpolationsformel für eine Art Symmetrischer Functionen und über Deren Anwendung, in "Math. Abh. der Akademie der Wissenschaften zu Berlin" (1860), pp.1–20.
  2. ^ A. Cayley: A Theorem on Trees  in Quarterly Journal of Mathematics 1889, pp. 376-378.
  Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica