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

Counting trees

Jera Stojko (2017) Counting trees. Diploma thesis.

Download (563Kb)


    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