title: Enumerazione di grafi
text: # Enumerazione di grafi
  
  Nell'ambito della matematica combinatoria, l'enumerazione di grafi descrive una classe di problemi di enumerazione combinatoria, nei quali un grafo diretto oppure indiretto è oggetto di calcolo algebrico, tipicamente in funzione del numero di vertici del grafo stesso. I problemi di questa classe ammettono sia una soluzione esatta come quelli di enumerazione algebrica, che una soluzione approssimata asintoticamente.
  
  I pionieri in questo campo della matematica discreta furono Pólya, Arthur Cayley e John Howard Redfield.
  
  ## Problemi labeled
  
  I vertici possono essere etichettati (in inglese: labeled) ovvero non etichettati (unlabeled). Nel primo caso, i vertici sono distinguibili l'uno dall'altro; nel secondo caso, invece, qualsiasi permutazione dei vertici forma il medesimo grafo e pertanto i vertici si dicono indisitnguibili ed equivalenti tra loro.
  
  Il teorema di enumerazione di Pólya, noto anche come teorema di Redfield–Pólya, è un importante strumento analitico per ricondurre i problemi unlabeled alla più semplice forma di quelli labeled, considerando ogni classe senza etichetta come una classe di simmetria di oggetti etichettati.
  
  ## Formule esatte di enumerazione
  
  Alcuni risultati teorici di particolare rilievo sono dati dalle seguenti formule esatteò.
  
  * il numero di grafi semplici indiretti etichettati che sono generati da un grafo di n vertici, è pari a $2^{n(n−1)/2}.;$
  * il numero di grafi semplici diretti etichettati che sono generati da un grafo di n vertici, è pari a $2^{n(n−1)}.;$
  * il numero $C_n$ di grafi connessi indiretti etichettati soddisfa la relazione di ricorrenza:
  
         $C_{n}=2^{n \choose 2}-{\frac {1}{n}}\sum _{k=1}^{n-1}k{n \choose k}2^{n-k \choose 2}C_{k}.$, che per n = 1, 2, 3,... restituisce i valori di $C_n:$ 1, 1, 4, 38, 728, 26704, 1866256,... descritti dalla sequenza A001187 nel progetto OEIS;
  * il numero di grafi ad albero liberi etichettati che sono generati da un grafo di n vertici, è pari a $n^{n−2}(formula$ di Cayley);
  * il numero di grafi a bruco, che sono generati da un grafo di n vertici, è pari a:
  
         $2^{n-4}+2^{\lfloor (n-4)/2\rfloor }.$
  