thumb|A címkézett, 2,3, illetve 4 csúcsú nem gyökeres fák teljes listája: fa 2 csúccsal, fa 3 csúccsal és 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,Kombinatorische Anzahlbestimmungen für Gruppen, Graphen und chemische Verbindungen. Acta Math. 68 (1937), 145-254 Cayley-t és Redfieldet.The theory of group-reduced distributions. American J. Math. 49 (1927), 433-455.
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.Harary and Palmer, p. 1. 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.Harary and Palmer, p. 3. Az n csúcsú, címkézett, irányított gráfok száma 2n(n − 1).Harary and Palmer, p. 5. Az n csúcsú, címkézett, összefüggő egyszerű gráfok száma, Cn kielégíti a következő rekurrenciarelációtHarary and Palmer, p. 7.
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
Kategória:Gráfok leszámlálása Kategória:Kombinatorika