Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: THEend8_
MATH367 Homework # 1
Problem 1 (13 points): 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, Manch-
ester, 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 different 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
We want to find the assignment of samples to hospitals which mini-
mizes the total cost of testing.
Questions:
1. Write down a cost matrix for this problem (2 points)
2. Draw a cost flow network representation for this problem (2 points)
3. Give the interpretation of a minimal element of the cost matrix in
terms of paths in a flow network (2 points)
4. Now apply the most suitable algorithm from Chapter 4 to find the min-
imal cost assignment of samples to hospitals. Explain the condition
that is used to determine when the algorithm ends. (7 points)
MATH367 Homework # 1
Problem 2 (12 points): We consider one possible algorithm for find-
ing minimal distances from the starting vertex s to all other vertices in a
weighted graph without negative-weight cycles. w (u, v) is the edge weight
for an edge joining vertices u and v. Like in Dijkstra’s algorithm, with each
vertex v in a graph we associate:
• a length label li (v), which will eventually converge to the minimal
distance d (s, v) from s to v, and i enumerates the iterations of the
algorithm,
• a vertex pi (v) which will be the vertex previous to v on the minimal-
weight path from s to v .
We will denote the total number of vertices in a graph by |V |.
The algorithm comprises the following steps, again resembling Dijk-
stra’s algorithm:
Initialization: Set l0 (s) = 0 and l0 (v) = +∞ for all vertices v 6= s.
Main iteration: Repeat the following steps for i = 1 . . . |V | − 1 (that is,
|V | − 1 times):
• For each edge (uv) in a graph
• If li−1 (u) + w (u, v) < li−1 (v)
– Set li (v) = li−1 (u) + w (u, v)
– Set pi (v) = u
• Otherwise set li (v) = li−1 (v).
End: When the main iteration is finished, the labels l|V |−1 (v) contain min-
imal distances d (s, v) from s to v, and the labels p|V |−1 (v) can be
used to reconstruct the minimal-weight paths from any vertex v to s,
like in Dijkstra’s algorithm
MATH367 Homework # 1
Figure 1: An example of a graph with negative edge weights.
Questions:
1. What is the complexity of this algorithm in large-O notation, ex-
pressed in terms of the number of vertices |V | and the number of
edges |E|? (2 points)
2. Apply this algorithm to the graph shown on Fig. 1 and check whether
it produces correct minimal distances from vertex A to all other ver-
tices (Dijkstra’s algorithm fails for this graph with negative-weight
edge) (3 points)
3. For a weighted graph G, let us consider a set Pi of paths which in-
clude not more than i edges. Let di (s, v) be the minimal path weight
among those paths in Pi which start at a vertex s and end at a ver-
tex v, if such paths exist. If it is not possible to connect s and v by
a path with not more than i edges we define di (s, v) = +∞. Prove
that after the i’th step of the main iteration in the above algorithm,
li (v) = di (s, v) for any vertex v in G. Use induction starting with
i = 0, when only l0 (s) = 0 < ∞, which is the weight of zero-length
path from s to itself. (3 points)
4. Prove that any path (that is, a walk which passes through all vertices
and edges not more than once) in a graph with |V | vertices includes
not more than |V | − 1 edges. (2 points)
5. Prove that if there are no negative-weight or zero-weight cycles in
a weighted graph, the minimal-weight walk between any two distinct
vertices is a path (that is, a walk which passes through all vertices
and edges not more than once) (2 points)