Preštevanje drevesStojko, Jera (Avtor) Kuzman, Boštjan (Mentor) grafV teoriji grafov drevo pomeni kombinatoričen objekt, ki ga običajno definiramo kot povezan graf brez ciklov. V nalogi je predstavljen problem preštevanja različnih dreves s podanim številom vozlišč. Podani so štirje dokazi znamenitega Cayleyevega izreka za število označenih dreves: dokaz s Prüferjevo bijektivno konstrukcijo, dokaz s preštevanjem zakoreninjenih dreves na dva načina J. Pitmana, dokaz z rekurzivno formulo za število označenih gozdov in dokaz z uporabo Kirchhoffove zveze med determinantami matrik in vpetimi drevesi. V zadnjem delu je izpeljan novejši rezultat A. China in ostalih, o verjetnosti, da je naključno izbrano drevo v polnem grafu vpeto drevo. Posebej je obravnavano obnašanje limitne vrednosti verjetnosti, ko število vozlišč polnega grafa raste čez vse meje. Dobljeni rezultat je presenetljiv in lep.20172017-09-23 02:57:00Diplomsko delo/naloga95887COBISS_ID: 11727689sl