HSC Critical Path Past Qs 2Blah blah blah blah blah blah blah eprc2;qeblag blah blah blha bka l/qchoWHVOHVOhveuHWVOHWOhvwoHV\'HB IEJKEC/ fbejvrbjrebjvrnvnrebvjbvjrbvjrbvjbrjvbjrbvjrbvjrbvjbrjvbjvbjbrvjbrjrbjrkea\'/\'vnreonvureohilehiovhc bv2uo3qci;i PDF

Preview

Summary

ghhfhdjsjiweejnnndjjs s ndhjd d,xllxlklms wbwhdhuduslw smkols,sklnjecbruic ;wc lhchcckeuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuqwnddddddddddddddddddddddddddddddddddduq;X QWINXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXAKoooooooooooooooooooomxwwoiuencoinnnnnnnnnnnnnnnnnnnnnnnn...

Description

Questions STD 2: Networks (Std 2), N3 Critical Path Analysis (Y12)

Flow Networks and Minimum Cuts Teacher: Katrina Giannikos Exam Equivalent Time: 60 minutes (based on HSC allocation of 1.5 minutes approx. per mark)

1.Networks, STD2 N3 2008 FUR1 1 MC Steel water pipes connect five points underground. The directed graph below shows the directions of the flow of water through these pipes between these points. 

OVERVIEW Networks is a new Std2 topic area and has been allocated an impressive 13% of the HSC exam in 2020 and 10% in 2019. We have split N3 Critical Path Analysis into two categories for the purposes of analysis: 1-Critical Paths and 2-Flow Networks and Minimum Cuts. This analysis will look at Flow Networks and Minimum Cuts. ANALYSIS Flow Networks and Minimum Cuts have caused surprising problems in the first two years of the new Std2 syllabus.

 The directed graph shows that water can flow from

Minimum Cut/Maximum Flow: this topic has been examined in both 2020 and 2019, in 3-mark questions that were both poorly answered.

A. point 1 to point 2.

"Reverse flows" (i.e. flows from sink to source across a minimum cut line) has proven a challenging concept and deserves revision attention. We recommend a careful review of 2019 Std2 HSC 40.

C. point 4 to point 1.

Network adjustments to increase flow has appeared in both the 2019 Std2 exam and the NESA Topic Guidance. We highly recommend reviewing examples of this question type which are easily identified using the sub-category filter in the program. In addition to more difficult problems, we've designed our database to also cover many lower band questions, in a similar style to the examples provided in official Topic Guidance and exemplar question releases from NESA.

B. point 1 to point 4.

D. point 4 to point 2.

2.Networks, STD2 N3 2006 FUR1 2 MC

4.Networks, STD2 N3 2006 FUR1 6 MC

The following directed graph represents a series of one-way streets with intersections numbered as nodes 1 to 8. 

 In the directed graph above the weight of each edge is non-zero. The capacity of the cut shown is  All intersections can be reached from

A. a + b + c + d + e B. a + c + d + e

A. intersection 4

C. a + b + c + e

B. intersection 5

D. a + b + c – d + e

C. intersection 6 D. intersection 8

5.Networks, STD2 N3 2012 FUR1 6 MC

3.Networks, STD2 N3 2014 FUR1 2 MC

 In the directed network diagram above, all vertices are reachable from every other vertex. All vertices would still be reachable from every other vertex if we remove the edge in the direction from A.

to

B.

to

In the directed graph above, the only vertex with a label that can be reached from vertex Y is

C.

to

A. vertex A

D.

to

B. vertex B C. vertex C D. vertex D

6.Networks, STD2 N3 2013 FUR1 9 MC

7.Networks, STD2 N3 2019 FUR1 3 MC

Alana, Ben, Ebony, Daniel and Caleb are friends. Each friend has a different age.

The flow of water through a series of pipes is shown in the network below

The arrows in the graph below show the relative ages of some, but not all, of the friends. For example, the arrow in the graph from Alana to Caleb shows that Alana is older than Caleb. 

The numbers on the edges show the maximum flow through each pipe in litres per minute. 

 Using the information in the graph, it can be deduced that the second-oldest person in this group of friends is A. Alana

 The capacity of Cut

B. Ben

A.

11

C. Caleb

B.

13

D. Ebony

C.

14

D.

17

, in litres per minute, is

8.Networks, STD2 N3 SM-Bank 42 MC

9.Networks, STD2 N3 SM-Bank 16 MC

The network diagram below flows from the source (S) to sink (T).

The network diagram represents a system of roads connecting a shopping centre to the motorway.

Which of the edges is not at maximum capacity? 

Two routes from the shopping centre connect to A and one route connects to D to F. The number on the edge of each road indicates the number of vehicles that can travel on it per hour.

 A. B. C. D.

At present, the capacity of the network from the shopping centre to the motorway is not maximised. Which additional road(s) would increase the network capacity to its maximum? A.

A road from A to F with a capacity of 20 vehicles per hour

B.

A road from B to E with a capacity of 30 vehicles per hour

C.

A road from C to F with a capacity of 30 vehicles per hour and a road from E to F with a capacity of 60 vehicles per hour

D.

A road from B to F with a capacity of 30 vehicles per hour and a road from D to F with a capacity of 30 vehicles per hour

10.Networks, STD2 N3 2008 FUR1 6 MC

12.Networks, STD2 N3 2009 FUR2 2 One of the landmarks in a city is a hedge maze. The maze contains eight statues. The statues are labelled to on the following directed graph. Walkers within the maze are only allowed to move in the directions of the arrows. 

 For the graph above, the capacity of the cut shown is A.  B.  C.  D. 

11.Networks, STD2 N3 2009 FUR1 3 MC

 a. Write down the two statues that a walker could not reach from statue b. One way that statue 

can be reached from statue

List the three other ways that statue

. (1 mark)

is along path

can be reached from statue

. . (1 mark)

13.Networks, STD2 N3 SM-Bank 34 The arrows on the diagram below show the direction of the flow of waste through a series of pipelines froma factory to a waste dump. The numbers along the edges show the number of megalitres of waste per week that can flow through eachsection of pipeline. 

 The maximum flow from source to sink through the network shown above is A.   B.   C. 

 The minimum cut is shown as a dotted line.

D.

Calculate the capacity of this cut, in megalitres of waste per week. (2 marks)

14.Networks, STD2 N3 SM-Bank 35

16.Networks, STD2 N3 SM-Bank 17

The following directed graph shows the flow of water, in litres per minute, in a system of pipes connecting the source to the sink. 

The network diagram represents a system of roads connecting a shopping centre to the motorway. Two routes from the shopping centre connect to A and one route connects D to F. The number on the edge of each road indicates the number of vehicles that can travel on it per hour. 

 Calculate the maximum flow, in litres per minute, from the source to the sink. (2 marks)

15.Networks, STD2 N3 SM-Bank 46 A network diagram is drawn below.   Draw additional road(s) on the diagram to maximise the capacity. Include the number of vehicles that can travel on each road. (2 marks)

  i. Calculate the maximum flow through this network. (2 marks) ii. Copy the network above and illustrate the maximum flow capacity. (2 marks)

17.Networks, STD2 N3 2018 FUR2 1

18.Networks, STD2 N3 SM-Bank 45

The graph below shows the possible number of postal deliveries each day between the Central Mail Depot and the Zenith Post Office.

An oil pipeline network is drawn below that shows the flow capacity of oil pipelines in kilolitres per hour. 

The unmarked vertices represent other depots in the region. The weighting of each edge represents the maximum number of deliveries that can be made each day. 

 A cut is shown. i. What is the capacity of the cut. (1 mark) ii. Calculate the minimum cut of this network? (2 marks) iii. Copy the network diagram, showing the maximum flow capacity of the network by labelling the flow of each edge. (2 marks)

19.Networks, STD2 N3 SM-Bank 36



In the network below, the values on the edges give the maximum flow possible between each pair of vertices. The arrows show the direction of flow. A cut that separates the source from the sink in the network is also shown. 

a. Cut A, shown on the graph, has a capacity of 10. 

Two other cuts are labelled as Cut B and Cut C. i. Write down the capacity of Cut B. (1 mark) ii. Write down the capacity of Cut C. (1 mark) b. Determine the maximum number of deliveries that can be made each day from the Central Mail Depot to the Zenith Post Office. (1 mark)

 i. Calculate the capacity of the cut shown in the diagram. (1 mark) ii. Calculate the maximum flow between source and sink. (2 marks)

20.Networks, STD2 N3 2020 HSC 30 The network diagram shoows a series of water channels and ponds in a garden. The vertices , , , , , and represent six ponds. The edges represent the water channels which connect the ponds. The numbers on the edges indicate the maximum capacity of the channels. 

21.Networks, STD2 N3 2019 HSC 40 A museum is planning an exhibition using five rooms. The museum manager draws a network to help plan the exhibition. The vertices , , , and represent the five rooms. The number on the edges represent the maximum number of people per hour who can pass through the security checkpoints between the rooms. 

 a. Determine the maximum flow of the network. (2 marks) b. A cut is added to the network, as shown. 

 a. What is the capacity of the cut shown? (1 mark) b. The museum manager is planning for a maximum of 240 visitors to pass through the exhibition each hour. By using the 'minimum cut-maximum flow' theorem, the manager determines that the plan does not provide sufficient flow capacity. 

Draw the minimum cut onto the network below and recommend a change that the manager could make to one or more security checkpoints to increase the flow capacity to 240 visitors per hour.  (2 marks)



 Is the cut shown a minimum cut? Give a reason for your answer. (1 mark)



Copyright © 2004-20 The State of New South Wales (Board of Studies, Teaching and Educational Standards NSW)

6.Networks, STD2 N3 2013 FUR1 9 MC

Worked Solutions 1.Networks, STD2 N3 2008 FUR1 1 MC



2.Networks, STD2 N3 2006 FUR1 2 MC



3.Networks, STD2 N3 2014 FUR1 2 MC 

4.Networks, STD2 N3 2006 FUR1 6 MC



7.Networks, STD2 N3 2019 FUR1 3 MC

5.Networks, STD2 N3 2012 FUR1 6 MC 8.Networks, STD2 N3 SM-Bank 42 MC 



9.Networks, STD2 N3 SM-Bank 16 MC

11.Networks, STD2 N3 2009 FUR1 3 MC

Motor way

73 30 F

B

97

E 90 Shopping Center

25

55

A

20

50

115

C

81

30

110



D



NOTTO SCALE

80

♦ Mean mark 44%.

39

 

10.Networks, STD2 N3 2008 FUR1 6 MC 12.Networks, STD2 N3 2009 FUR2 2 

♦♦ Mean mark 35%. MARKER'S COMMENT: For an individual flow to contribute to the "cut", it must flow from the source to the sink.

a.  b. 

13.Networks, STD2 N3 SM-Bank 34



14.Networks, STD2 N3 SM-Bank 35

 

15.Networks, STD2 N3 SM-Bank 46

16.Networks, STD2 N3 SM-Bank 17

i.  Motor way

73 30 F

B

97

E 90



   ii. 

Shopping Center

25

55

A

20

50

115

C

81

30

110

D NOTTO SCALE

80 39

17.Networks, STD2 N3 2018 FUR2 1

18.Networks, STD2 N3 SM-Bank 45

a.i. 

i. 







 a.ii. 

ii.





 b. 







♦♦ COMMENT: Be very careful! RS is not included as it goes from sink to source.

♦ Mean mark part (b) 32%. COMMENT: Review carefully! Most common incorrect answer was 9.



  iii. 

19.Networks, STD2 N3 SM-Bank 36

21.Networks, STD2 N3 2019 HSC 40

i. 

a.  ♦ Mean mark part (a) 50%. COMMENT: A quarter of students incorrectly included the "8" which is flowing in the opposite direction.

 ii.





b.  

♦♦ Mean mark 32%. COMMENT: In part (a), edge BC flows from the exit to the entry and is therefore not counted.

♦♦ Mean mark part (b) 24%. ♦♦♦ Mean mark 19%. COMMENT: In part (b), edge BC now flows from entry to exit in the new "minimum" cut and is counted.

20.Networks, STD2 N3 2020 HSC 30 a. 

Copyright © 2016-2021 M2 Mathematics Pty Ltd (SmarterMaths.com.au)



♦ Mean mark 41%.

  b.   

♦♦ Mean mark 28%.

 ...