MATH 367 NETWORKS IN THEORY AND PRACTICE
NETWORKS IN THEORY AND PRACTICE
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: THEend8_
MATH 367
DEPARTMENT: Mathematical Sciences
EXAMPLE 2 EXAMINATIONS
NETWORKS IN THEORY AND PRACTICE
Time allowed: Two and a half hours
INSTRUCTIONS TO CANDIDATES: Candidates should attempt
all questions. Full marks will be awarded for complete answers to all
questions.
Paper Code MATH 367 Page 1 of 5 CONTINUED
1. (a) Give the definition for
(i) a complete graph, [2 marks]
(ii) an empty graph, [1 mark]
(iii) a bipartite graph, [2 marks]
(iv) a complete bipartite graph. [1 mark]
(b) Is the graph below bipartite? If your answer is “yes”, find the partition
X and Y.
v8 v7
v6v5
v4 v3
v2v1
[4 marks]
(c) The digraph Γ has the following adjacency matrix
A =
0 1 0 1 0
0 0 0 1 1
1 0 0 1 0
0 1 1 0 1
0 0 0 1 0
where the entry in the i-th row and j-th column is equal to the number
of arcs from the vertex vi to the vertex vj.
(i) Find the indegrees and the outdegrees of the vertices v1 and v4.
[2 marks]
(ii) State in details a well-known criterion and use it to deduce that the
digraph is strongly connected. [6 marks]
(iii) Is Γ a simple digraph? Justify your answer. [2 marks]
2. In the flow network N shown below, S is the source, F is the sink and the
number on each arc represents its capacity
Paper Code MATH 367 Page 2 of 5 CONTINUED
(i) Give the definition for a cut and for the capacity of a cut. [2 marks]
(ii) Calculate the capacity of the cut ({S,A,B,C}, {D,E, F,G}). What can
you deduce about the value of any flow in N? [2 marks]
(iii) Prove that for every cut P, P˜ :
f(N) ≤ K(P, P˜ ) ,
where
K(P, P˜ ) =
∑
u∈P,v∈P˜
c(u, v) and f(N) =
∑
u∈P,v∈P˜
f(u, v)−
∑
u∈P,v∈P˜
f(v, u) .
[3 marks]
(iv) Use the Berge’s superior path method to find a complete flow in the
network. [6 marks]
(v) Starting from this flow, use the Ford-Fulkerson algorithm to find a max-
imal flow in the network. [5 marks]
(vi) Find the associated cut for the maximal flow, and confirm the “minimal
cut - maximal flow” theorem. [2 marks]
3. (a) (i) State the conditions for an undirected graph to contain an Euler
tour. [2 marks]
(ii) State for which value of n the complete graphs Kn contain an Euler
tour. [3 marks]
(iii) State for which values of r and s the complete bipartite graphs Kr,s
contain an Euler tour. [3 marks]
(iv) A graph G possesses 39 edges and an Euler tour. How do you know
that G is not bipartite? [2 marks]
Paper Code MATH 367 Page 3 of 5 CONTINUED
(b) The length lij of each edge (Xi, Xj) of the undirected graph G = (V,E)
is given by the matrix L = (lij):
L =
0 2 7 8 ∞ ∞
2 0 3 9 10 ∞
7 3 0 4 ∞ ∞
8 9 4 0 5 2
∞ 10 ∞ 5 0 4
∞ ∞ ∞ 2 4 0
The distance dij of the shortest path in G between vertices Xi and Xj
is given by the matrix D = (dij):
D =
0 2 5 8 12 10
2 0 3 7 10 9
5 3 0 4 9 6
8 7 4 0 5 2
12 10 9 5 0 4
10 9 6 2 4 0
Use matrices L and D to:
(i) Calculate the length of a Chinese Postman’s tour of G.
[6 marks]
(ii) Derive a Chinese Postman’s tour of G. [4 marks]
4. (a) (i) Give the definition of the Hamiltonian (Hamilton) tour.
[3 marks]
(ii) Prove that if the Hamiltonian tour in the graph G exists, and we
leave out any k vertices with adjacent edges to the graph G, then
the remaining graph G∗ has at most k connected components.
[5 marks]
(b) A project involving 5 tasks is to be undertaken by a project team con-
taining 5 people. Each task must be assigned to a single member of
the team and no team member might be assigned more than one task.
The time in which team member i is expected to complete task j is tij.
The time estimates for all team members and tasks are comprised in the
matrix T = tij given below:
T =
14 17 20 19 19
16 12 19 18 21
15 13 21 20 22
14 17 17 15 21
17 13 19 18 22
.
Paper Code MATH 367 Page 4 of 5 CONTINUED
(i) Use the Hungarian method (Method of Lines) to determine the
assignment of team members to tasks for which the total time taken
to complete the five tasks is minimised. [10 marks]
(ii) What is the total time taken to complete all tasks? [2 marks]
5. (a) Part of a one-way traffic system in a UK city is shown below,
with the direction of the flows and the capacity of each section of the
roads. In addition, junctions A and B have capacities 17 and 12, respec-
tively. Model the system using the flow network framework, and find
the maximum steady flow through the system. [8 marks]