HW #7 – The Prüfer Correspondence

Due March 19 at 3:30 PM

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. Your assignment is to implement his 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 list, S, is called the Prüfer Code of T.

Hints on 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. There are different types of trees, but in our case, edges will be bidirectional (that means that if T[i][j] is true, T[j][i] must necessarily be true), and T[i][i] will always be false (a vertex can't be connected to itself).

You may assume that the input trees are valid trees. (But do check that the labels the user enters are integers, rather than characters, for example.)

In this assignment, since the trees' vertices are numbered from 1 to n, we'll have one extra row and column Here's a representation for the following tree with 5 vertices (all the trees in this assignment will have no more than 5 vertices). 

    0  1  2  3  4  5 
  0 -  -  -  -  -  -      
  1 -  F  T  F  F  F       	Tree:  1-2-3-4-5

  2 -  T  F  T  F  F

  3 -  F  T  F  T  F     

  4 -  F  F  T  F  T     

  5 -  F  F  F  T  F

(Note that the dashes in the 0 row and column would actually be set to false; I put them there so it would be easier to see the important parts of the matrix.)

The Prüfer Code of a tree, S, with n vertices can easily be represented as an integer array containing n-2 elements.

Sample Output

This program will prompt you for a description of a 5-vertex tree,
display the tree, and calculate its Pruefer Code.

Please enter the 4 edges of your tree, one at a time.

Edge #1
First Vertex: 1
Second Vertex: 2

Edge #2
First Vertex: 2
Second Vertex: 3

Edge #3
First Vertex: 3
Second Vertex: 4

Edge #4
First Vertex: 2
Second Vertex: 5

The tree is given by the following matrix:

    0  1  2  3  4  5

0   0  0  0  0  0  0
1   0  0  1  0  0  0
2   0  1  0  1  0  1
3   0  0  1  0  1  0
4   0  0  0  1  0  0
5   0  0  1  0  0  0

The Pruefer Code is: 0 2 3 2 0

Press any key to continue

Back to Main Page