Топ-100
Indietro

ⓘ Formula di Cayley. La formula di Cayley è usata in matematica nella teoria dei grafi. Essa afferma che il numero di alberi ricoprenti che si possono costruire s ..




Formula di Cayley
                                     

ⓘ Formula di Cayley

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

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 vedi immagine a destra, per alberi con 2, 3 e 4 vertici la formula fornisce i seguenti risultati:

  • A 4 = 4 − 2 {\displaystyle A_{4}=4^{4-2}} 16 alberi con 4 vertici
  • A 3 = 3 − 2 {\displaystyle A_{3}=3^{3-2}} 3 alberi con 3 vertici
  • A 2 = 2 − 2 {\displaystyle A_{2}=2^{2-2}} 1 albero con 2 vertici
                                     

1. Storia

Questa formula fu scoperta dal tedesco Carl Borchardt nel 1860, che la dimostrò tramite un determinante. Nel 1889 linglese 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 nelluso.

                                     

2. Dimostrazioni

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.

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

P = {\displaystyle P=x_{1},x_{2},x_{3}.,x_{n-2}}

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

                                     
  • da Arthur Cayley Cayley nel suo lavoro riconobbe la paternità della scoperta a Borchardt, ma oggi la formula è nota come formula di Cayley Altri progetti
  • da Gustav Kirchhoff, ed è una generalizzazione della formula di Cayley che fornisce il numero di alberi ricoprenti in un grafo completo. Dato un grafo
  • il teorema di Hamilton - Cayley il cui nome è dovuto a William Rowan Hamilton e Arthur Cayley asserisce che ogni trasformazione lineare di uno spazio
  • generati da un grafo di n vertici, è pari a nn  2 formula di Cayley il numero di grafi a bruco, che sono generati da un grafo di n vertici, è pari a:
  • rappresentazione della formula di struttura di un composto chimico mediante l utilizzo di un grafo. La sua introduzione si ritiene dovuta a Arthur Cayley il quale
  • gruppo di Klein eccetto l identità hanno periodo 2. È un abeliano, e isomorfo al gruppo diedrale di ordine 4. La tabella di Cayley del gruppo di Klein
  • ultime memorie di Jacobi, Sylvester 1839 e Arthur Cayley cominciano a lavorare su questi temi. Lo studio dei determinanti di matrici di forma speciale
  • la formula di Grassmann è una relazione che riguarda le dimensioni dei sottospazi vettoriali di uno spazio vettoriale o dei sottospazi proiettivi di uno
  • adattando una procedura di Aaron Williams per costruire un cammino hamiltoniano sul grafo di Cayley di un gruppo simmetrico, lo scrittore di fantascienza Greg
  • trasformarli in un albero. Questo risultato è chiamato formula di Cayley Il numero degli alberi con n vertici di grado d1, d2, ..., dn è n 2 d 1 1 d 2 1
  • trasposta di una matrice è la matrice ottenuta scambiandone le righe con le colonne. Fu introdotta nel 1858 dal matematico britannico Arthur Cayley La trasposta
  • quaternioni un caso particolare del teorema più generale oggi chiamato Teorema di Cayley - Hamilton Hamilton inventò anche il calcolo icosiano che usò per indagare