PrueferCode - Maple Help

GraphTheory

 PrueferCode
 compute Pruefer code

 Calling Sequence PrueferCode(L) PrueferCode(T)

Parameters

 T - tree L - list, Vector, or Array of positive integers

Description

 • PrueferCode(L) returns a tree which corresponds to the Prüfer encoding of L. The input L must be a list, Vector, or 1-D Array whose elements are positive integers less than or equal to numelems(L)+2.
 • PrueferCode(T) returns a list of positive integers comprising the Prüfer encoding of a tree T.

Examples

 > $\mathrm{with}\left(\mathrm{GraphTheory}\right):$
 > $\mathrm{PrueferCode}\left(\left[6,7,1,5,2,3,11,4,9,12\right]\right)$
 ${\mathrm{Graph 1: an undirected unweighted graph with 12 vertices and 11 edge\left(s\right)}}$ (1)
 > $T≔\mathrm{Graph}\left(10,\left\{\left\{1,8\right\},\left\{2,3\right\},\left\{2,7\right\},\left\{4,6\right\},\left\{5,6\right\},\left\{6,7\right\},\left\{6,8\right\},\left\{7,9\right\},\left\{8,10\right\}\right\}\right)$
 ${T}{≔}{\mathrm{Graph 2: an undirected unweighted graph with 10 vertices and 9 edge\left(s\right)}}$ (2)
 > $\mathrm{PrueferCode}\left(T\right)$
 $\left[{8}{,}{2}{,}{7}{,}{6}{,}{6}{,}{7}{,}{6}{,}{8}\right]$ (3)

Details

 • The Prüfer encoding of a tree was first used by Heinz Prüfer to prove Cayley's formula, which states that the number of trees on n labeled vertices is ${n}^{n-2}$.

References

 "Prüfer sequence", Wikipedia. https://en.wikipedia.org/wiki/Pruefer_sequence

Compatibility

 • The GraphTheory[PrueferCode] command was introduced in Maple 2021.