diplomsko delo
Jera Stojko (Avtor), Boštjan Kuzman (Mentor)

Povzetek

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.

Ključne besede

graf;polni graf;drevo;vpeto drevo;preštevanje;Cayleyev izrek;verjetnost;faktor;

Podatki

Jezik: Slovenski jezik
Leto izida:
Tipologija: 2.11 - Diplomsko delo
Organizacija: UL PEF - Pedagoška fakulteta
Založnik: [J. Stojko]
UDK: 519.17(043.2)
COBISS: 11727689 Povezava se bo odprla v novem oknu
Št. ogledov: 810
Št. prenosov: 185
Ocena: 0 (0 glasov)
Metapodatki: JSON JSON-RDF JSON-LD TURTLE N-TRIPLES XML RDFA MICRODATA DC-XML DC-RDF RDF

Ostali podatki

Sekundarni jezik: Angleški jezik
Sekundarni naslov: Counting trees
Sekundarni povzetek: 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.
Sekundarne ključne besede: mathematics;matematika;
Vrsta datoteke: application/pdf
Vrsta dela (COBISS): Diplomsko delo/naloga
Komentar na gradivo: Univ. v Ljubljani, Pedagoška fak., Dvopredmetni učitelj: Fizika-matematika
Strani: [43] str.
ID: 10865631
Priporočena dela:
, diplomsko delo
, magistrsko delo
, diplomsko delo
, delo diplomskega seminarja
, diplomsko delo