Enumerazione di grafi
# 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 }.$
