Dokazi Cayleyeve formule

diplomski rad

• Naslov (engleski): Proofs of Cayley's formula
• Autor: Patricija Dovijanić
• Mentor: Vedran Krčadinac (mentor)
• Član povjerenstva: Vedran Krčadinac (predsjednik povjerenstva)
• Član povjerenstva: Boris Širola (član povjerenstva)
• Član povjerenstva: Igor Pažanin (član povjerenstva)
• Član povjerenstva: Sonja Štimac (član povjerenstva)
• Ustanova koja je dodijelila akademski / stručni stupanj: Sveučilište u Zagrebu; Prirodoslovno-matematički fakultet; (Matematički odsjek); Zagreb
• Datum i država obrane: 2024-03-01, Hrvatska
• Znanstveno / umjetničko područje, polje i grana: PRIRODNE ZNANOSTI; Matematika

Sažetak

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.

Sažetak (engleski)

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.

• Ključne riječi: Pruferovi kodovi; Joyalova bijekcija; Riordanov dokaz; Renyijev dokaz; Pitmanov dokaz
• Ključne riječi (engleski): Prufer codes; Joyal’s bijection; Riordan proof; Renyi’s proof; Pitman’s proof
• Jezik: hrvatski
• URN:NBN: urn:nbn:hr:217:272993
• Studijski program: Naziv: Matematička statistika; Vrsta studija: sveučilišni; Stupanj studija: diplomski; Akademski / stručni naziv: sveučilišni magistar matematike (univ. mag. math.)
• Vrsta resursa: Tekst
• Način izrade datoteke: Izvorno digitalna
• Prava pristupa: Otvoreni pristup
• Datum i vrijeme pohrane: 2024-03-13 09:05:44