Math Thesis Archive

Home Personnel Programs Jobs Computing Organization Information Research menubar


How to encode a tree


Sally Picciotto

We construct bijections giving three ``codes'' for trees. These codes follow naturally from the Matrix Tree Theorem of Tutte and have many advantages over the one produced by Pr\"ufer in 1918. One algorithm gives explicitly a bijection that is implicit in Orlin's manipulatorial proof of Cayley's formula (the formula was actually found first by Borchardt). Another is based on a proof of Knuth. The third is an implementation of Joyal's pseudo-bijective proof of the formula, and is equivalent to one previously found by E{\u{g}}ecio{\u{g}}lu and Remmel. In each case, we have at least two algorithms, one of which involves hands-on manipulations of the tree while the other involves a combinatorial and linear algebraic manipulation of a matrix.

Home | Personnel | Programs |Jobs | Computing | Organization | Department | Research