Macaulay2 » Documentation
Packages » AllMarkovBases » pruferSequence
next | previous | forward | backward | up | index | toc

pruferSequence -- the edge set of a spanning tree corresponding to a Prüfer sequence

Description

Cayley's formula in graph theory is the result that the number of trees with vertices labelled from $0$ to $n-1$ is $n^{n-2}$. The Prüfer sequence of a labelled tree is an element of $\{0, \dots, n-1\}^{n-2}$ and gives an explicit bijection between the two sets.

This function produces the edge set of the spanning tree corresponding to a given Prüfer sequence.

i1 : pruferSequence {2}

o1 = {set {0, 2}, set {1, 2}}

o1 : List
i2 : pruferSequence {1,3}

o2 = {set {0, 1}, set {1, 3}, set {2, 3}}

o2 : List
i3 : pruferSequence {3,3,3,4}

o3 = {set {0, 3}, set {1, 3}, set {2, 3}, set {4, 3}, set {4, 5}}

o3 : List

Ways to use pruferSequence:

  • pruferSequence(List)

For the programmer

The object pruferSequence is a method function.


The source of this document is in /build/reproducible-path/macaulay2-1.25.06+ds/M2/Macaulay2/packages/AllMarkovBases.m2:827:0.