Prüferliste

A Prüferliste, also known as a Prüfer sequence or Prüfer code, is a unique sequence of numbers associated with a labeled tree. Specifically, it is a sequence of length n-2, where n is the number of vertices in the tree, and each vertex is labeled with an integer from 1 to n. The Prüfer sequence is generated using a specific algorithm that iteratively removes the leaf node with the smallest label.

The algorithm for constructing a Prüfer sequence for a given labeled tree proceeds as follows: find the leaf node with the smallest label. Remove this node and its incident edge from the tree. The label of the neighbor of the removed leaf node is appended to the Prüfer sequence. This process is repeated until only two nodes remain in the tree. The resulting sequence of n-2 labels is the Prüfer sequence for the tree.

Conversely, a Prüfer sequence can be used to uniquely reconstruct the labeled tree from which it was derived. The reconstruction algorithm involves a set of available nodes (initially 1 to n) and the given Prüfer sequence. For each number in the Prüfer sequence, we find the smallest available node that is not present in the sequence up to that point. An edge is then added between this node and the current number from the sequence. Both the node and the number from the sequence are then marked as used. This process continues until the Prüfer sequence is exhausted, at which point the two remaining unused nodes form the final edge.

Prüfer sequences have applications in various areas of graph theory and combinatorics, particularly in problems related to counting labeled trees and studying their properties. The bijection between labeled trees and Prüfer sequences is a fundamental result in this field.