20.500.12556/RUL-162402 Dokazi Cayleyjeve formule magistrsko delo Proofs of Cayley's formula V magistrskem delu obravnavamo Cayleyjevo formulo, ki pravi, da je vseh označenih dreves na $n$ vozliščih $n^{n-2}$. Vsestranskost te formule spoznamo preko raznolikosti njenih dokazov. Spoznamo dokaze, ki temeljijo na bijekciji med množicama z isto kardinalnostjo, kot so Pitmanov, Joyalov in Pruferjev dokaz. Ogledamo si rekurzivne zveze med drevesi, ki temeljijo na indukciji po vozliščih drevesa. Naučimo se, kako lahko procese razvejanja povežemo z naključnimi sprehodi in to uporabimo pri dokazovanju. Predstavimo Laplaceovo matriko in izrek o številu vpetih dreves ter s prijemi iz linearne algebre pokažemo veljavnost Cayleyjeve formule. Spoznamo pa tudi uporabnost eksponentnih rodovnih funkcij za štetje označenih dreves in Lagrangeevo inverzijo. In this thesis we discuss Cayley's formula, which states that there are $n^{n-2}$ labelled trees on $n$ vertices. The versatility of this formula can be seen through the diversity of its proofs. We are introduced to bijection based proofs between sets of the same cardinality, such as Pitman's, Joyal's and Prufer's proof. We get to know recursive tree relations that can be proved by induction on the number of vertices. We learn about links between the branching process and random walks and use them in proofs. Using knowledge of linear algebra as well as introducing the Laplacian matrix and the Matrix-tree theorem we show that Cayley's formula holds. We also present the usability of exponential generating functions for counting labelled trees along with Lagrange's inversion theorem. Cayleyjeva formula označeno drevo drevo s korenom rodovne funkcije proces razvejanja Laplaceova matrika Cayley's formula labelled tree rooted tree generating functions branching process Laplacian matrix true false false Slovenski jezik Angleški jezik Magistrsko delo/naloga 2024-09-22 08:15:04 2024-09-22 08:15:08 2024-09-25 03:51:27 0000-00-00 00:00:00 2024 0 0 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 519.17 143995 208470275 12530.pdf 12530.pdf 1 D34540FA9F12D449FB2DAC11E48F6071 34532e499da22ea4598dbb33086faca714d5a037f25975cdb8818953d96b5667 e6342284-78a9-11ef-b232-0050569b8976 https://repozitorij.uni-lj.si/Dokument.php?lang=slv&id=191716 Fakulteta za matematiko in fiziko 0 0 0