Gráfok leszámlálása

A címkézett, 2,3, illetve 4 csúcsú nem gyökeres fák teljes listája: $2^{2-2}=1$ fa 2 csúccsal, $3^{3-2}=3$ fa 3 csúccsal és $4^{4-2}=16$ fa 4 csúccsal.

A kombinatorika és gráfelmélet területén a gráfok leszámlálása a kombinatorikai leszámlálási problémák olyan osztálya, melyben adott paraméterekkel rendelkező irányítatlan vagy irányított gráfokat kell megszámlálni, általában a gráfok csúcsainak függvényében. Ezek a problémák vagy egzakt módon vagy aszimptotikusan oldhatók meg. A terület úttörői közé sorolják Pólyát, Cayley-t és Redfieldet.

Címkézett és nem címkézett problémák

Egyes gráfleszámlálási problémákban a gráfok csúcsait úgy tekintjük, hogy „címkézve” vannak, ezért megkülönböztethetőek egymástól, míg más problémák esetében a csúcsok bármilyen permutációját ugyanannak a gráfnak tekintjük. Az általános tapasztalat szerint a címkézett problémák könnyebben megoldhatók, mint a címke nélküliek. Mint a kombinatorikai leszámlálási problémáknál általában, a Pólya-módszer a gráfok szimmetriáinak kezelésében is hasznos eszköznek bizonyult.

Egzakt leszámlálási képletek

A terület néhány fontos eredménye:

• Az n csúcsú, címkézett, irányítatlan gráfok száma 2^{n(n − 1)/2}.
• Az n csúcsú, címkézett, irányított gráfok száma 2^n(n − 1).
• Az n csúcsú, címkézett, összefüggő egyszerű gráfok száma, C_n kielégíti a következő rekurrenciarelációt

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

amiből könnyen kiszámíthatók C_n értékei n = 1, 2, 3, …-ra: 1, 1, 4, 38, 728, 26704, 1866256, ...(A001187 sorozat az OEIS-ben)

• Az n csúcsú, címkézett nem gyökeres fák száma n^n − 2 (Cayley-formula).
• Az n csúcsú, nem címkézett hernyógráfok száma

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