SmarterEd

Aussie Maths & Science Teachers: Save your time with SmarterEd

Networks, GEN1 2024 VCAA 36 MC

Eight houses in an estate are to be connected to the internet via underground cables.

The network below shows the possible connections between the houses.

The vertices represent the houses.

The numbers on the edges represent the length of cable connecting pairs of houses, in metres.
 

 

The graph that represents the minimum length of cable needed to connect all the houses is
 


 

Show Answers Only

\(D\)

Show Worked Solution

\(\text{Consider all options}\)

\(\text{Option A: contains a circuit}\ \rightarrow\ \text{Eliminate A}\)

\(\text{Option B:}\ 19+18+16+15+16+14+18=116\)

\(\text{Option C:}\ 20+19+18+16+15+16+14=118\)

\(\text{Option D:}\ 19+18+16+15+16+14+17=115\)

\(\Rightarrow D\)

Networks, GEN1 2022 VCAA 1 MC

The network below shows the distances, in kilometres, along a series of roads.

The vertices \(A, B, C, D, E, F, G\) and \(H\) represent the intersections of these roads.
 

Prim's algorithm can be used to find the

  1. critical path.
  2. shortest path.
  3. minimum cut.
  4. minimum allocation.
  5. minimum spanning tree.
Show Answers Only

\(E\)

Show Worked Solution

Prim’s algorithm is used to find the minimum spanning tree.

\(\Rightarrow E\)

NETWORKS, FUR1 2019 VCAA 5 MC

The following diagram shows the distances, in metres, along a series of cables connecting a main server to seven points, `A` to `G`, in a computer network.
 


 

The minimum length of cable, in metres, required to ensure that each of the seven points is connected to the main server directly or via another point is

  1. 175
  2. 203
  3. 208
  4. 221
  5. 236
Show Answers Only

`B`

Show Worked Solution

`text(Using Prim’s Algorithm:)`

`text{Edge 1: main server to D (15)}`

`text{Edge 2: DE (28)}`

`text{Edge 3: EG (30)}`

`text{Edge 4: GF (32)}`

`text{Edge 5: EA (35)}`

`text{Edge 6: AB (28)}`

`text{Edge 7: GC (35)}`
 

`:.\ text(Minimum length)`

`= 15 + 28 + 30 + 32 + 35 + 28 + 35`

`= 203\ text(m)`

`=>  B`

NETWORKS, FUR1 2018 VCAA 2 MC

Niko drives from his home to university.

The network below shows the distances, in kilometres, along a series of streets connecting Niko’s home to the university.

The vertices `A`, `B`, `C`, `D` and `E` represent the intersection of these streets.
 


 

The shortest path for Niko from his home to the university could be found using

  1. a minimum cut.
  2. Prim’s algorithm.
  3. Dijkstra’s algorithm.
  4. critical path analysis.
  5. the Hungarian algorithm.
Show Answers Only

`C`

Show Worked Solution

`text(Djikstra’s algorithm can be used to find the)`

`text(shortest path.)`

`text(Note that Prim’s algorithm can be used to)`

`text(find the minimum spanning tree but doesn’t)`

`text(necessary provide the shortest path from 2)`

`text(nominated vertices.)`

`=> C`