Gráfok leszámlálása

A címkézett, 2,3, illetve 4 csúcsú nem gyökeres fák teljes listája: ${\displaystyle 2^{2-2}=1}$ fa 2 csúccsal, ${\displaystyle 3^{3-2}=3}$ fa 3 csúccsal és ${\displaystyle 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.^[1] 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,^[2] Cayley-t^[3] és Redfieldet.^[4]

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.^[5] 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}.^[6]
• Az n csúcsú, címkézett, irányított gráfok száma 2^n(n − 1).^[7]
• 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^[8]

${\displaystyle 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^[9]

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

Jegyzetek

1. Graphical Enumeration. Academic Press (1973). ISBN 0-12-324245-2 
2. Kombinatorische Anzahlbestimmungen für Gruppen, Graphen und chemische Verbindungen. Acta Math. 68 (1937), 145-254
3. "Cayley, Arthur (CLY838A)". A Cambridge Alumni Database. University of Cambridge.^{[halott link]}
4. The theory of group-reduced distributions. American J. Math. 49 (1927), 433-455.
5. Harary and Palmer, p. 1.
6. Harary and Palmer, p. 3.
7. Harary and Palmer, p. 5.
8. Harary and Palmer, p. 7.
9. Harary, Frank & Schwenk, Allen J. (1973), "The number of caterpillars", Discrete Mathematics 6 (4): 359–365, DOI 10.1016/0012-365x(73)90067-8.