Enumerazione di grafi

L'elenco completo di tutti i grafi ad albero liberi generati da 2,3,4 vertici etichettati: o $2^{2-2}=1$ albero per 2 vertici, $3^{3-2}=3$ grafi ad albero per 3 vertici e $4^{4-2}=16$ per 4 vertici.

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 }.$