From Wikipedia, the free encyclopedia
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]
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.
A terület néhány fontos eredménye:
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.