MATH367 Networks in Theory and Practice Tutorial Homework # 4
Please hand in your solutions to problem 1.
1. An undirected graph G with vertices 1, 2, . . . , 6 has edge lengths lij = lji between
vertices i and j given in matrix form by
L = (lij) =

0 ∞ 13 8 ∞ 14
∞ 0 ∞ 3 11 16
13 ∞ 0 4 10 ∞
8 3 4 0 3 ∞
∞ 11 10 3 0 5
14 16 ∞ ∞ 5 0

where lij =∞ means that there is no edge between i and j. The length dij of the
shortest path between i and j is given by the matrix
D = (dij) =

0 11 12 8 11 14
11 0 7 3 6 11
12 7 0 4 7 12
8 3 4 0 3 8
11 6 7 3 0 5
14 11 12 8 5 0

Use this information to find a minimal postman’s tour of G and its length.
2. In the following flow network N , S is the source, F is the sink and the number
above the edges gives the capacity
(i) Find the capacity of the cut S, A, B, C and D, E, F, G.
(ii) Use the Berge’s superior path method to find a flow in the network N which
has a bottleneck edge on every directed path from S to F. (A bottleneck edge
is one on which the flow is equal to the capacity of the edge). Find the value
of this flow through N.
(iii) Find the maximal flow in the network.
1
3. A milkman and his assistant deliver milk to several houses on streets whose length
is shown in the map below. They start and finish their tour at point A and can
deliver milk to houses on both sides of the street at the same time. They use the
route A → Y → Z → F → Y → X → Z → E → B → E → D → F → D →
C → A→ X → B → C → A
a) How can this route be improved?
b) If the assistant is not available, the milkman can only deliver milk to one side of
the street. Find the least distance for a delivery route in this case, assuming
that there are houses on both sides of every street, except around the open
space area, which has houses on one side only.
2

欢迎咨询51作业君