prikaz prve stranice dokumenta Dokazi Cayleyeve formule
  Download
PDF 460.32 KB
master's thesis
Dokazi Cayleyeve formule
Zagreb: University of Zagreb, Faculty of Science, 2024. urn:nbn:hr:217:272993
Dovijanić, Patricija
University of Zagreb
Faculty of Science
Department of Mathematics

Institutional repository: Repository of the Faculty of Science

Cite this document

Dovijanić, P. (2024). Dokazi Cayleyeve formule (Master's thesis). Zagreb: University of Zagreb, Faculty of Science. Retrieved from https://urn.nsk.hr/urn:nbn:hr:217:272993

Dovijanić, Patricija. "Dokazi Cayleyeve formule." Master's thesis, University of Zagreb, Faculty of Science, 2024. https://urn.nsk.hr/urn:nbn:hr:217:272993

Dovijanić, Patricija. "Dokazi Cayleyeve formule." Master's thesis, University of Zagreb, Faculty of Science, 2024. https://urn.nsk.hr/urn:nbn:hr:217:272993

Dovijanić, P. (2024). 'Dokazi Cayleyeve formule', Master's thesis, University of Zagreb, Faculty of Science, accessed 23 December 2024, https://urn.nsk.hr/urn:nbn:hr:217:272993

Dovijanić P. Dokazi Cayleyeve formule [Master's thesis]. Zagreb: University of Zagreb, Faculty of Science; 2024 [cited 2024 December 23] Available at: https://urn.nsk.hr/urn:nbn:hr:217:272993

P. Dovijanić, "Dokazi Cayleyeve formule", Master's thesis, University of Zagreb, Faculty of Science, Zagreb, 2024. Available at: https://urn.nsk.hr/urn:nbn:hr:217:272993

Metadata
TitleDokazi Cayleyeve formule
Title (english)Proofs of Cayley's formula
AuthorPatricija Dovijanić
MentorVedran Krčadinac (mentor)
Committee memberVedran Krčadinac (predsjednik povjerenstva)
Committee memberBoris Širola (član povjerenstva)
Committee memberIgor Pažanin (član povjerenstva)
Committee memberSonja Štimac (član povjerenstva)
GranterUniversity of Zagreb
Faculty of Science
(Department of Mathematics)
Zagreb
Defense date and country2024-03-01, Croatia
Scientific / art field,
discipline and subdiscipline		NATURAL SCIENCES
Mathematics
Abstract
U ovom radu proučavamo Cayleyevu formulu i njene dokaze. Najprije uvodimo osnovne pojmove teorije grafova i iskaz Cayleyeve formule. Zatim prelazimo na njene odabrane dokaze, počevši s bijektivnim dokazima: dokaz pomoću Pruferovih kodova, dokaz Joyalovom bijekcijom te dokaz pomoću funkcija parkiranja. Potom provodimo dokaze koji se temelje na matematičkoj indukciji: dokaz formulom uključivanja-isključivanja te Riordanov i Renyijev dokaz. Slijede dokazi dvostrukim prebrojavanjem: Pitmanov dokaz preko usmjerenih stabala, dokaz preko razapinjućih stabala i Clarkeov dokaz pomoću prespajanja. Zatim obrađujemo Polyin dokaz preko funkcija izvodnica i Lagrangeove formule inverzije. Kao primjer matričnog dokaza dajemo dokaz Kirchhoffovim matričnim teoremom o stablima. Završavamo vjerojatnosnim dokazom preko Poissonovog procesa grananja.
Abstract (english)
In this thesis, we study Cayley’s formula and its various proofs. First, we introduce basic graph theory notation and the statement of Cayley’s formula. We then move on to a selection of its proofs, starting with bijective proofs: a proof using Prufer codes, a proof using Joyal’s bijection, and a proof using parking functions. Then we carry out proofs based on mathematical induction: a proof using the principle of inclusion and exclusion, and Riordan and Renyi’s proof. Proofs by double counting follow: Pitman’s proof via directed trees, a proof via spanning trees, and Clarke’s proof using linkages of trees. We continue by covering Polya’s proof via generating functions and Lagrange’s inversion formula. We also present a proof using Kirchhoff’s matrix-tree theorem. We conclude with a probabilistic proof using a Poisson branching process.
Keywords
Keywords (english)
Languagecroatian
URN:NBNurn:nbn:hr:217:272993
Study programmeTitle: Mathematical Statistics
Study programme type: university
Study level: graduate
Academic / professional title: sveučilišni magistar matematike (sveučilišni magistar matematike)
Type of resourceText
File originBorn digital
Access conditionsOpen access
Terms of useLicence In copyright icon
Created on2024-03-13 09:05:44