MATH10001 Mathematical Workshop

Graphs, Trees and Algorithms Part 2

Questions start on page 3

Trees

Recall that a simple graph is one without loops or multiple edges. We are interested in a special type of simple graph:

A tree is a simple connected graph with no cycles.(i.e. no paths (u, v1 , ..., vn- 1 , u) of length > 1 from a vertex u to itself). Any vertex of degree 1 in a tree is known as a leaf.

Trees with 1,2,3 and 4 vertices

In this lecture we will attempt to answer the following question.

How many trees can we construct on n vertices, labelled 1,2,...,n?

This question was originally answered by the English mathematician Arthur Cayley in 1889. We will prove Cayley’s theorem, not in the same way as Cayley but using a method devised by the German mathematician Heinz Prfer. His approach is to use an algorithm to construct a code from a tree. By showing that there are the same number of codes as trees we can then enumerate the trees on n vertices.

From Trees to Prfer Codes

We now explain how to encode our trees as sequences of numbers. For simplicity we will assume our vertices are labelled {1, 2, ..., n}.

A Prfer code on n > 2 is a sequence of numbers (s1 , s2 , ..., sn-2 ) where si e {1, ..., n} for each i = 1, ..., n - 2.

For example (3, 1, 1, 4, 4, 4) and (3, 4, 5, 6, 7, 8) are two Prfer codes on n = 8.

Algorithm PC1 (Prfer Code 1)

INPUT: a tree T with vertex set {1, ..., n} where n > 2

OUTPUT: a Prfer code PC1(T) on n.

(step 1) i = 1

(step 2) j = smallest leaf of T , and suppose the incident edge is e = jk

(step 3) si = k and T := T with e and j removed.

(step 4) if i = n - 2, output (s1 , ..., sn-2 ) = PC1(T ) and STOP;

otherwise i := i + 1 and go to step 2.

From Prfer Codes to Trees

We now introduce an algorithm that performs the reverse task to PC1.

We need the following notation: for a Prfer code (s1 , ..., sn-2 ) on n let o(j) be the number of occurrences of the number j in the Prfer code, for j = 1, ..., n.

Algorithm PC2 (Prfer Code 2)

INPUT: a Prfer code P = (s1 , s2 , ..., sn-2 ) on n

OUTPUT: a tree with edge set E and vertex set {1, ..., n}

(step 1) i = 1 and E = 

(step 2) j = the smallest integer with o(j) = 0 and E := E u {jsi}.

(step 3) o(j) = - 1 and o(si) = o(si) - 1

(step 4) if i = n - 2 go to step 5, otherwise i := i + 1 and go to step 2.         (step 5) E := E u {kl} where o(k) = o(l) = 0 and o(j) = - 1 for all other j. (step 6) output PC2(P) = T the tree with edge set E and STOP.

Example

Run PC2 on the Prfer code P = (6, 4, 6, 3)

Theorem

For any Prfer code P and tree T , P = PC1(T) if and only if T = PC2(P).

Proof

By induction on the number of vertices. Details not included in this project.

MATH10001 Mathematical Workshop

Problems for part 2

Problem 4

Draw diagrams for all trees, up to isomorphism, with 5 vertices. For each diagram, how many trees are there with vertex set {1, 2, 3, 4, 5}? In each case show how you arrived at your answer.

Problem 5

Let T be a tree with n vertices.

(i) Prove that there is a unique path between any two vertices in T .

(ii) Use induction on n to prove that T has n - 1 edges. (Hint: for the induction step, remove an edge from T and consider the resulting graph.)

Problem 6

Run PC1 on the tree T with adjacency table:

Then run PC2 on the output to get back to T . Write out all the steps in both algorithms.

Project Report

The assessment for this project is by an individual project report.

The report should contain your solutions to the six problems and the homework for part 1. Your report should be well presented and the problem solutions should be clearly explained.

Even though you have worked as a group on this project, the report should be all your own work. There are marks for the clarity as well as the correctness of your mathematical arguments.