Arthur Cayley first proved that there are \(n^{n-2}\) labeled trees on \(n\) vertices, and in another proof of the same theorem, Heinz Prüfer showed a bijection between trees on \(n\) vertices and \((n-2)\)-tuples of integers from 1 to \(n – 2\), called Prüfer codes. The proof provides an algorithm that allows us to construct an arbitrary labeled tree from its code.
The algorithm proceeds as follows:
- Initialise an array of node degrees for the nodes, which are numbered from 1 to \(n + 2\)
- For each occurrence of a node number in the code, increment its degree
- Add 1 to all degrees
- For each occurrence of a node number in the code:
- Find the lowest-numbered node with degree 1
- Create an edge between that node and the node in the code
- Decrement the degrees of both nodes by 1
- There are now 2 nodes left with degree 1, so join them with an edge to complete the tree
Below is an implementation of the algorithm in C. The function prufer_tree()
takes a code in the form of an array of unsigned integers and its length, and returns the tree as an array of edges.
#include <stdlib.h> typedef struct { unsigned int first; unsigned int second; } edge; edge *prufer_tree(const unsigned int *code, size_t len) { unsigned int i, j, e = 0; const unsigned int n = len + 2; /* Nodes */ edge *tree = malloc((n - 1) * sizeof(edge)); unsigned int *degrees = calloc(n + 1, sizeof(unsigned int)); /* 1-based */ if (tree == NULL || degrees == NULL) { free(tree); free(degrees); return NULL; } /* Set the degrees from the occurrences in the code */ for (i = 0; i < len; i++) { degrees[ code[i]]++; } /* Add 1 to them all */ for (i = 1; i <= n; i++) { degrees[i]++; } /* Add edges to nodes in the code */ for (i = 0; i < len; i++) { /* Find the lowest-numbered node with degree 1 */ for (j = 1; degrees[j] != 1; j++); /* Add the edge */ tree[e].first = j; tree[e].second = code[i]; degrees[j]--; degrees[ code[i]]--; e++; } /* Find the last 2 degree-1 nodes */ for (i = 1; degrees[i] != 1; i++); for (j = i + 1; degrees[j] != 1; j++); /* Add the last edge */ tree[e].first = i; tree[e].second = j; free(degrees); return tree; }
Here is an example program that constructs the tree in the image at the top:
#include <stdio.h> #include <stdlib.h> int main(void) { unsigned int code[] = {1, 1, 1, 1, 6, 5}; const size_t len = sizeof(code) / sizeof(unsigned int); const unsigned int n = len + 1; /* Edges */ edge *tree = prufer_tree(code, len); unsigned int e; for (e = 0; e < n; e++) { printf("(%u, %u)\n", tree[e].first, tree[e].second); } free(tree); return 0; }
The output:
(2, 1) (3, 1) (4, 1) (7, 1) (1, 6) (6, 5) (5, 8)