20.500.12556/RUL-95887 Preštevanje dreves Counting trees V 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. In graph theory, trees are combinatorial objects usually defined as connected graphs without cycles. In this thesis, the problem of counting different trees with a given number of vertices is presented. Four proofs of a celebrated theorem on the number of labeled trees by A. Cayley are given: by using a bijective construction due to H. Prüfer, by double counting of labeled rooted trees due to J. Pitman, by establishing a recursion on the number of labeled forests, and finally, by applying a relation between determinants and spanning trees due to H. Kirchhoff. In the final part, a recent result by A. Chin et al. is presented on the probability that a randomly picked tree in a complete graph is a spanning tree. In particular, the limit of this value as the number of vertices approaches infinity is observed. The result obtained is both surprising and beautiful. graf graph true false false Slovenski jezik Angleški jezik Diplomsko delo/naloga 2017-09-23 02:57:00 2017-09-25 12:35:51 2025-04-17 04:53:21 0000-00-00 00:00:00 2017 0 0 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 11727689 Prestevanje_dreves_-_diplomsko_delo.pdf Prestevanje_dreves_-_diplomsko_delo.pdf 1 0048E7333E33406857994931609C0729 ab6dddb311989420798c4a8e56b1b05c628ee35bb6dc9eecd0d387c4382e8288 220bdf8f-1aaf-11f0-b232-0050569b8976 https://repozitorij.uni-lj.si/Dokument.php?lang=slv&id=205736 Pedagoška fakulteta 0 0 0