Wyliczanie wykresów

Pełna lista wszystkich wolnych drzew na wierzchołkach oznaczonych 2, 3 i 4:

{\ Displaystyle 2 ^ {2-2} = 1}

drzewo z 2 wierzchołkami,

= 3} drzewa z

{\ Displaystyle 3

wierzchołkami

i drzewa z 4

W kombinatoryce , dziedzinie matematyki , wyliczanie grafów opisuje klasę kombinatorycznych problemów wyliczania , w których należy policzyć nieskierowane lub skierowane grafy pewnych typów, zazwyczaj w funkcji liczby wierzchołków grafu. Problemy te można rozwiązać albo dokładnie (jako z wyliczaniem algebraicznym ), albo asymptotycznie . Pionierami w tej dziedzinie matematyki byli George Pólya , Arthur Cayley i J. Howarda Redfielda .

Problemy oznaczone i nieoznaczone

W niektórych problemach z wyliczaniem graficznym uważa się, że wierzchołki grafu są oznaczone w taki sposób, aby można je było odróżnić od siebie, podczas gdy w innych problemach uważa się, że każda permutacja wierzchołków tworzy ten sam graf, więc wierzchołki są uważane za identyczne lub nieoznakowane . Ogólnie rzecz biorąc, oznaczone problemy wydają się być łatwiejsze. Podobnie jak w przypadku bardziej ogólnego wyliczania kombinatorycznego, twierdzenie Pólya o wyliczaniu jest ważnym narzędziem do redukowania problemów nieoznakowanych do oznaczonych: każda klasa nieoznakowana jest uważana za klasę symetrii oznakowanych obiektów.

Dokładne wzory wyliczeniowe

Oto niektóre ważne wyniki w tej dziedzinie.

Liczba oznaczonych n -wierzchołków prostych grafów nieskierowanych wynosi 2 ^{n ( n −1)/2} .
Liczba oznaczonych n -wierzchołków prostych grafów skierowanych wynosi 2 ^{n ( n −1)} .
Liczba C _n spójnych , oznaczonych n -wierzchołków nieskierowanych grafów spełnia zależność rekurencji

{\ Displaystyle C_ {n} = 2 ^ {n \ wybierz 2} - {\ Frac {1} {n}} \ suma _ {k = 1} ^ {n-1} k {n \ wybierz k} 2 ^ {nk \choose 2}C_{k}.}

z którego łatwo obliczyć dla n = 1, 2, 3, ..., że wartości dla C _n to

1, 1, 4, 38, 728, 26704, 1866256, ... (sekwencja A001187 w OEIS )

Liczba oznaczonych drzew wolnych od n -wierzchołków wynosi n ^{n −2} ( wzór Cayleya ).
Liczba nieoznakowanych gąsienic n - wierzchołków wynosi

{\ Displaystyle 2 ^ {n-4} + 2 ^ {\ lfloor (n-4) / 2 \ rfloor}.}

Baza danych wykresów

Różne grupy badawcze udostępniły przeszukiwalną bazę danych, która zawiera listę wykresów o pewnych właściwościach o małych rozmiarach. Na przykład