[feed] pefprints@pef.uni-lj.si | [feed] Atom [feed] RSS 1.0 [feed] RSS 2.0 |
slovenščina
Logo            
  Logo Login | Create Account
 
 

Counting trees

Jera Stojko (2017) Counting trees. Diploma thesis.

[img]
Preview
PDF
Download (563Kb)

    Abstract

    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.

    Item Type: Thesis (Diploma thesis)
    Keywords: graph, complete graph, tree, spanning tree, enumerating, Cayley's Theorem, probability
    Number of Pages: 43
    Language of Content: Slovenian
    Mentor / Comentors:
    Mentor / ComentorsIDFunction
    doc. dr. Boštjan KuzmanMentor
    Link to COBISS: http://www.cobiss.si/scripts/cobiss?command=search&base=50126&select=(ID=11727689)
    Institution: University of Ljubljana
    Department: Faculty of Education
    Item ID: 4723
    Date Deposited: 22 Sep 2017 10:47
    Last Modified: 22 Sep 2017 10:47
    URI: http://pefprints.pef.uni-lj.si/id/eprint/4723

    Actions (login required)

    View Item