2014 Networks AT 4.1
In 2014 St Leonard’s College celebrates its centenary year. Many events have been organised to acknowledge this proud achievement.
Question 1.
One of the events was a Centenary Surf Carnival for Old Collegians held atTorquay. Many old collegians travelled from great distances to attend the day. The following network represents the routes linking 5towns,Torquay at A and St Leonard’s College at G. The distance in kilometres along each road is shown in the diagram.
a)In this network, what is the length of the shortest route from Torquay at A, to St Leonard’s College at G?
20 + 27 + 41 = 88
[1 mark]
b)What is the degree of vertex B?
4
[1 mark]
c)Explain why the above graph is planar and show how to use Euler’s formula to verify this.
No edges cross each other.
Euler’s formula: v + f = e + 2
[3 marks]
d)What is the degree sum of the above graph?
S = 2e
= 2 × 11
= 22
[1 mark]
e)At present it is not possible to travel along each road in this network once and only once starting at A and returning to A.
(i)However, it is possible to start somewhere else and travel along every road once only. If we wished to do this, where would we need to start and finish?
D and F
(ii)Why did you choose your answer to e) (i)?
because these vertices have odd degree
(iii)Which towns would need to be linked by an additional road tomake it possible to start at A, travel along each road once only and return to A?
D and F
(iv)What is the name of this type of route?
Euler Circuit
[1 + 1 + 1 +1 = 4 marks]
f)The towns are also linked by a telecommunications grid. The cable of this grid runs along the road network. Draw the minimal-length spanning tree forthe cable network on the diagram below.
[2 marks]
g)What is the minimum length of cable required for the telecommunications grid?
166
[1 mark]
h)It was suggested that the school might provide a bus to Torquay. The route would start at St Leonard’s and go to each town once only, ending at Torquay.
(i)What is the name of this type of path?
Hamilton Path
(ii)Write down the shortest possible path and state its length.
G-F-E-D-B-C-A
175
[1 + 2 = 3 marks]
Question 2
One of the Old Collegians runs a very profitable business. As a guest speaker she discussed the reasons for her success. She explained that the hierarchy of her business is outlined by the directed network below where each vertex represents an employee.
a)Determine which employees have one-step dominance over employee D.
A, B and E
[1 mark]
b)Complete the adjacency matrix below to show the one stage dominance in the network above.
[2 marks]
c)With one stage dominance, there is no single employee who is dominant over all the other employees. Explain why.
Because B and D are both dominant over three people each.
[2 marks]
d)Write down the matrixM2.
[1 mark]
e)Calculate M + M2
[2 marks]
f)Hence, determine which employee has the greatest influence.
B is the most dominant.
[2 marks]
Question 3
Another celebration for the Centenary is a ball for the Parents at the National Gallery of Victoria. This will include a private viewing of the Italian Masterpieces Exhibition. The following network diagram shows the number of people able to view the art works in each roomat 20 minute intervals starting at A and finishing at G.
a)What is the value of Cut 1?
37
[1 mark]
b)What is the maximum flow in the network?
30
[1 mark]
c)On the diagram above draw the cut that represents the maximum flow.
[1 mark]
An extra room connecting C and F is added to the diagram. It has a value of 10 people.
d)Cut 2is not a valid cut when trying to find the minimum cut from A to G. Why?
Because it does not cut the flow from the source to the sink.
[1 mark]
e)What is the maximum flow in the network as a result of this improvement?
37
[1 mark]
Question 4
In planning all the events a number of tasks needed to be completed in a particular order.
This planning project can be represented by the graph below. Each edge represents a task and the number represents the duration of the task in days.
a)List all the tasks that must be completed before task E is commenced.
A, B and C
[1 mark]
b)Use the information given on the graph to complete following table.
Task / Earliest start time / Latest start timeA / 0 / 0
B / 0 / 1
C / 6 / 7
D / 10 / 10
E / 10 / 11
F / 14 / 14
G / 14 / 18
H / 18 / 20
I / 18 / 18
J / 23 / 23
K / 22 / 24
[3 marks]
c)For this project
(i)Write down the critical path
A-D-F-I-J
(ii)Determine the length of the critical path.
27 days
[1 + 1 = 2 marks]
d)What is the float time for activity H?
2 days
[1 mark]
e)Activity G was to send to each Old Collegian a beautifully printed invitation to the event. Unfortunately the delivery of the special paper chosen was delayed as the company initially chosen went bankrupt. What is the maximum number of additional days that this delay could occur without delaying the whole project?
4 days
[1 mark]
f)If the organisers of the events are prepared to pay for additional labour in finding and contacting past collegians, the time taken to complete task A can be reduced to 8 days, task E can be reduced to 5 days and task I can be reduced to 4 days.
Make the above changes on the following graph
(i)Is it worthwhile reducing all the tasks A, E and I? If not, which tasks should not be reduced and why?
- Not worth reducing E at all as it is not on the critical path.
- It IS worth reducing I by one day.
- It is only worth reducing A by one day as if it went down to 8 days then it would no longer be on the Critical path. ie B and C will still take 9 days to be completed so it is only worthwhile reducing A to 9 days.
[3 marks]
(ii)What would be the new critical path(s)?
A-D-F-I-J
and B-C-D-F-I-J
(iii)How long would it now take to complete the project?
25 days
[2 + 1 = 3marks]
g)It turns out that activity H also has activity B as an immediate predecessor. On the diagram below, insert a labelled dummy activity in the appropriate place to reflect this.
[1 mark]
h)Does this new dummy activity change the critical path?
No.
[1 mark]
Page 1 of 9