Chris Hanusa Math 381 – Homework 2 Answer Key October 22, 2003

Question 1 – Consider the matrix

(\begin{matrix}0 & 1 & 0 & 0 & 1 & 1 \\ 1 & 0 & 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 1 & 0 \\ 1 & 1 & 0 & 1 & 0 & 0 \\ 1 & 0 & 1 & 0 & 0 & 0 \end{matrix})  (1)

Draw the graph defined by this adjacency matrix.

(a) Is this graph connected? How many edges does it have? Find the longest path. Is there a cycle in this graph? Answer these questions using the drawing of the graph.

(b) Answer the same questions using only the matrix.

Answer – From the adjacency matrix, we can come up with a graph.

                        [Everyone got it.]

(a) Looking at the graph, we see that the graph is connected and there are 7 edges. The longest path is the path that visits the most vertices without repetition. Therefore the maximum length for the longest path is 6 − 1 = 5, and this is attained by visiting the following vertices in order: {4, 5, 1, 2, 3, 6}. There are indeed cycles in the graph. There are three, one of which visits the vertices {5, 2, 3, 6, 1} and returns to vertex 5.

(b) From the matrix, we know that the matrix is connected because either A^{6} contains no 0 entries or because vertex 1 is in contact with vertices 2,5, and 6, vertex 2 touches vertex 3 and vertex 5 touches vertex 4. The number of edges can be determined by summing the entries of the matrix and dividing by two, giving 7, as before. The longest path possible is of length 5, which we can find by starting at (4,5), traveling vertically to (2,5), traveling horizontally to (2,3), traveling vertically to (6,3), and traveling horizontally to (6,1). Lastly, there is a loop since there is a rectangle (1,2), (1,6), (3,2), (3,6). Alternatively, we know that there is cycle because there are more than n − 1 edges for a graph on n vertices.

Question 2 – Give a proof that the “pessimistic” algorithm for the minimum spanning tree problem gives an optimum tree.

Answer [10 points] – (a) There are a number of valid approaches to this problem, but you must be careful that you prove all your assertions. We will show that the pessimistic algorithm gives exactly the same tree as given by the Optimistic Algorithm.

The Optimistic Algorithm orders the edges of the graph and starts adding the edges with the smallest weight unless a cycle is formed. The pessimistic algorithm orders the edges of the graph and subtracts the edges with the largest weight unless the graph becomes disconnected. Considering the edges that are added versus those that are taken away, we notice that an edge is only taken away if it is an edge in a cycle somewhere, because if not, it would disconnect the graph. Therefore this edge would not be added in the Optimistic Algorithm. Hence the tree generated by the pessimistic algorithm is exactly a tree that would be generated by the Optimistic Algorithm.

Since we know that the Optimistic Algorithm gives a minimum spanning tree for any graph, that implies that the tree given by the pessimistic algorithm is a minimum spanning tree of the graph. •

Question 3 – Determine all the different unlabelled trees on 5 vertices. Then find how many labellings each of them can have (to check your result, use the Cayley-formula: there are n^{n−2} different labeled trees on n vertices).

Answer [10 points] – There are three distinct unlabeled trees on 5 vertices, being as follows:

• − • − • − • − •
•
|
• − • − •
|
•
•
|
• − • − •
|
•

As for labeled trees, we consider how to label the vertices of the three possible unlabeled trees above.

In the first tree, we have 5 possibilities for the first vertex, 4 for the second, 3 for the third, and 2 for the fourth. But because of the symmetry of the tree, we are overcounting by two times. Therefore there are 5!/2 = 60 ways to label the first tree.

In the second tree, we have 5 possibilities for the first vertex, 4 for the second, 3 for the third, and because the last two vertices are indistinguishable, those are all the choices we have. Therefore there are 5 · 4 · 3 = 60 ways to label the second tree.

In the first tree, once we label the center vertex, the other four vertices are indistinguishable. Therefore the one choice we have is of 5 center vertices, so there are 5 ways to label the third tree.

Summing over the three possibilities, there are a total of 60 + 60 + 5 = 125 labeled trees on 5 vertices. We should expect this because 5^{3} = 125.