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)