Gráfok leszámlálása
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 2n(n − 1)/2.
Az n csúcsú, címkézett, irányított gráfok száma 2n(n − 1).
Az n csúcsú, címkézett, összefüggő egyszerű gráfok száma, Cn kielégíti a következő rekurrenciarelációt

amiből könnyen kiszámíthatók Cn értékei n = 1, 2, 3, …-ra: 1, 1, 4, 38, 728, 26704, 1866256, ...
Az n csúcsú, címkézett nem gyökeres fák száma nn − 2 (Cayley-formula).
Az n csúcsú, nem címkézett hernyógráfok  száma

Jegyzetek

Gráfok leszámlálása
Kombinatorika
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 ( n − 1) /2 . Az n csúcsú , címkézett , irányított gráfok száma ( n − 1) . Az n csúcsú , címkézett , összefüggő egyszerű gráfok száma , Cn kielégíti a következő rekurrenciarelációt amiből könnyen kiszámíthatók Cn értékei n = …-ra :\ . . . Az n csúcsú , címkézett nem gyökeres fák száma nn − 2 ( Cayley-formula ) . Az n csúcsú , nem címkézett hernyógráfok száma Jegyzetek Gráfok leszámlálása Kombinatorika