MATH367 Specimen Class test II
Problem 1: Graph Isomorphisms
1. Explain how many di erent graphs are isomorphic to the following graph and draw the isomorphic graphs. (3 points)
2. A tree T has 1 vertex of degree 2, 4 vertices of degree 3 and k vertices of degree 1. Find possible values of k. (2 points) Is there only one tree T (up to isomorphisms) that satis es the conditions set in the problem? (2 points)
Problem 2: Minimal spanning trees and algorithm com-plexity
We need to choose an algorithm for nding minimal spanning trees in a class of networks {G,wt} such that the underlying graphs G are planar and only have faces bounded by m = 3 edges. The number of vertices of G can become arbitrarily large, and the weights of edges can also be arbitrary positive numbers. Will Prim's or Kruskal's algorithm be more computationally e cient for this class of graphs? Justify your answer. (7 points)
Problem 3: Chinese postman problem
Streets and junctions in a small village can be represented in terms of the following network, where each junction is a vertex, and each street is represented by an edge. The weights of edges are the lengths of the streets.
Find out what would be the shortest possible length (length=sum of weights on all edges) of a walk for a postman who has to walk along each street at least once. You don't need to construct a postman's walk explicitly, just nd the minimal possible length. (8 points)
Problem 4: Assignment problem
Some company has produced four samples of a new COVID vaccine, which have code names of A, B, C, and D. The company needs to test these samples at hospitals in Liverpool, Manchester, Nottingham and Plymouth in such a way that no two samples can be tested in the same hospital, and no two hospitals can test the same sample. The costs of testing at di erent hospitals are (in thousands of pounds):
● Liverpool: Sample A - 88, Sample B - 76, Sample C - 45, Sample D - 23
● Manchester: Sample A - 7, Sample B - 68, Sample C - 86, Sample D - 8
● Nottingham: Sample A - 30, Sample B - 69, Sample C - 57, Sample D - 32
● Plymouth: Sample A - 24, Sample B - 51, Sample C - 52, Sample D - 55
Apply the most suitable algorithm from Chapter 4 to nd the minimal cost assignment of samples to hospitals. Explain the condition that is used to deter- mine when the algorithm ends. (8 points)