Nell'ambito della matematica combinatoria, lenumerazione 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ólyaKombinatorische Anzahlbestimmungen für Gruppen, Graphen und chemische Verbindungen, in Acta Math, 68 (1937), pp. 145-254, Arthur Cayley e John Howard Redfield.The theory of group-reduced distributions. American J. Math. 49 (1927), 433-455.
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 labeledHarary e Palmer, p. 1., 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 2n(n − 1)/2.Harary and Palmer, p. 3.; il numero di grafi semplici diretti etichettati che sono generati da un grafo di n vertici, è pari a 2n(n − 1).Harary and Palmer, p. 5.; il numero Cn di grafi connessi indiretti etichettati soddisfa la relazione di ricorrenzaHarary e Palmer, p. 7.: , che per n = 1, 2, 3,... restituisce i valori di Cn: 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 nn − 2(formula di Cayley); il numero di grafi a bruco, che sono generati da un grafo di n vertici, è pari a.:
Note
Categoria:Teoria dei grafi Categoria:Combinatoria algebrica