The Prüfer Correspondence

Introduction

A graph (in computer science) is a set of vertices (represented by dots) connected by edges (represented by lines). The degree of any vertex is the number of edges that join it to the rest of the graph. A tree is a special kind of graph, in which there are no cycles – that is, there’s no path from any one vertex back to itself. (This means that there are always at least two vertices with degree 1.) A labelled tree has its vertices labelled (usually, as in this assignment, with numbers).

The German mathematician Ernst Paul Heinz Prüfer discovered that any labelled tree (T) with n vertices can be uniquely represented by a list (S) of n-2 integers.

Prüfer's Algorithm

To find the sequence, S, given a tree, T:

  1. Choose the vertex of degree one of T with the smallest label
  2. Take the (unique) vertex of T adjacent to the vertex in (1) and make its label the first term in the sequence S.
  3. Remove the vertex in (1) and its adjacent edge from T
  4. Repeat these steps until there are only two vertices left in T. The resulting ordered set is called the Prüfer Code of T.

To find the matching tree, T, given the Prüfer Code, S:

  1. Draw n vertices, labelled 1, 2, ..., n, and also make a list 1,2,...,n
  2. Find the smallest number which is in the list 1,2,...,n but not in S, and join the vertex with this label to the vertex whose label is the first number in S, by an edge.
  3. Remove the first number in S from S and the number in (2) from the list.
  4. Repeat these steps until there are only two numbers left in the list and then join the vertices with these two labels by an edge.

Implementation

A tree with n vertices can be represented by a two-dimensional boolean array, T, with n rows and n columns. T[i][j] will be true if vertex i is connected to vertex j. This algorithm deals only with bidirectional edges, which means that if T[i][j] is true, T[j][i] must necessarily be true. Also, T[i][i] will always be false (since there are no cycles, a vertex can't be connected to itself).

It is assumed that the input trees are valid trees, except for the rudimentary check that no vertex is connected directly to itself.

Since the trees' vertices are numbered from 1 to n, we have one extra row and column in the matrix. Here's a representation for the following tree with 5 vertices. 

	Tree:  1-2-3-4-5

    0  1  2  3  4  5 

  0 -  -  -  -  -  -      

  1 -  F  T  F  F  F       

  2 -  T  F  T  F  F			

  3 -  F  T  F  T  F     

  4 -  F  F  T  F  T     

  5 -  F  F  F  T  F
The Prüfer Code of a tree, S, can easily be represented as an integer array containing n-2 elements. Finally, the list in the second half of the algorithm is represented by a boolean array of n elements.

Program

The code is in the file pruefer.cpp.

The executable version of the program (Windows only) is pruefer.exe.

Acknowledgements and History

The treatment of this problem from which the algorithm was taken is found on page 94 of Discrete Mathematics, by Washburn, Marlowe, and Ryan. (Addison Wesley Longman, (C) 2000)

This project grew out of a homework I assigned to my ENGR 131 recitation; that assignment is here.

Revisions of 3/9/2001 (suggested by Prof. Alexander):
- Performs the algorithm starting from either a tree or the Prüfer Code
- Checks to make sure that vertices are not connected directly to themselves

Revisions of 3/19/2001 (also suggested by Prof. Alexander):
- Recovers gracefully from the crash created by entering an invalid tree
- Checks to make sure that edges are unique at the time of entry