A supermarket has five departments, with areas allocated as shown on the floorplan below. The floorplan is represented by the graph below. On this graph, vertices represent departments and edges represent boundaries between two departments. This graph is incomplete. --- 0 WORK AREA LINES (style=lined) --- Karla is standing in the Promotional department. She wants to visit each department in the supermarket once only. --- 1 WORK AREA LINES (style=lined) --- --- 1 WORK AREA LINES (style=lined) --- \begin{aligned} --- 0 WORK AREA LINES (style=lined) --- a. b.ii. \(\text{Hamiltonian Path}\) c. a. b.i. \(\text{Bakery}\) b.ii. \(\text{The path has no repeated edges or vertices, and }\) \(\text{incudes all the edges of the graph.}\) \(\therefore\ \text{It is a Hamiltonian Path.}\) c.
& \ \ B \ \ \ D \ \ \ E \ \ \ F \ \ \ G \ \ \ P \\
\begin{array}{c}
B\\
D \\
E \\
F \\
G \\
P
\end{array}& \begin{bmatrix}
0 & 1 & 1 & 1 & 0 & 1 \\
1 & 0 & 0 & 1 & 1 & 0 \\
1 & 0 & 0 & 0 & 0 & 1 \\
1 & 1 & 0 & 0 & 1 & 1 \\
0 & 1 & 0 & 1 & 0 & 1 \\
1 & 0 & 1 & 1 & 1 & 0
\end{bmatrix}
\end{aligned}
b.i. \(\text{The bakery}\)
Networks, GEN1 2022 VCAA 2 MC
The map below shows seven countries within Central America.
A network diagram was drawn with seven vertices to represent each of the countries on the map of Central America. Edges were drawn to represent a border shared between two countries.
The number of edges that this network has is
- 5
- 6
- 7
- 8
- 9
Show Worked Solution
There are 7 edges.
\(\Rightarrow C\)
♦ Mean mark 49%.
Networks, GEN1 2023 VCAA 37 MC
The adjacency matrix below represents a planar graph with five vertices.
\begin{aligned}
& \ \ \ J\ \ \ K\ \ \ L\ \ M\ \ N \\
& {\left[\begin{array}{lllll}
0 & 1 & 0 & 1 & 1 \\
1 & 0 & 2 & 1 & 1 \\
0 & 2 & 0 & 1 & 1 \\
1 & 1 & 1 & 0 & 1 \\
1 & 1 & 1 & 1 & 0
\end{array}\right] \begin{array}{l}
J \\
K \\
L \\
M \\
N
\end{array}} \\
\end{aligned}
The number of faces on the planar graph is
- 5
- 7
- 9
- 15
- 17
Show Worked Solution
\(\text{Sketch network:}\)
\(\Rightarrow B\)
NETWORKS, FUR2 2021 VCAA 1
Maggie's house has five rooms, `A, B, C, D` and `E`, and eight doors.
The floor plan of these rooms and doors is shown below. The outside area, `F`, is shown shaded on the floor plan.
The floor plan is represented by the graph below.
On this graph, vertices represent the rooms and the outside area. Edges represent direct access to the rooms through the doors.
One edge is missing from the graph.
- On the graph above, draw the missing edge. (1 mark)
--- 0 WORK AREA LINES (style=lined) ---
- What is the degree of vertex `E`? (1 mark)
--- 1 WORK AREA LINES (style=lined) ---
- Maggie hires a cleaner to clean the house.
- It is possible for the cleaner to enter the house from the outside area, `F`, and walk through each room only once, cleaning each room as he goes and finishing in the outside area, `F`.
- i. Complete the following to show one possible route that the cleaner could take. (1 mark)
--- 0 WORK AREA LINES (style=lined) ---
ii. What is the mathematical term for such a journey? (1 mark)
--- 1 WORK AREA LINES (style=lined) ---
Show Answers Only
-
- `2`
- i. `FABEDCF\ text(or)\ FCDEBAF`
- ii. `text{Hamiltonian cycle}`
Show Worked Solution
a.
b. `text{Degree} = 2`
c.i. `FABEDCF\ text(or)\ FCDEBAF`
c.ii. `text{Hamiltonian cycle}`
NETWORKS, FUR2 2016 VCAA 1
A map of the roads connecting five suburbs of a city, Alooma (`A`), Beachton (`B`), Campville (`C`), Dovenest (`D`) and Easyside (`E`), is shown below.
- Starting at Beachton, which two suburbs can be driven to using only one road? (1 mark)
--- 2 WORK AREA LINES (style=lined) ---
A graph that represents the map of the roads is shown below.
One of the edges that connects to vertex `E` is missing from the graph.
- i. Add the missing edge to the graph above. (1 mark)
(Answer on the graph above)
--- 0 WORK AREA LINES (style=lined) ---
- ii. Explain what the loop at `D` represents in terms of a driver who is departing from Dovenest. (1 mark)
--- 2 WORK AREA LINES (style=lined) ---
Show Answers Only
a. `text(Alooma and Easyside.)`
b.i.
b.ii. `text(The loop represents that a driver can take a route out)`
`text(of Dovenest and return home without going through another)`
`text(suburb or turning back.)`
Show Worked Solution
a. `text(Alooma and Easyside.)`
| b.i. | |
`text(Draw a third edge between Easyside and Dovenest.)`
b.ii. `text(The loop represents that a driver can take a)`
♦♦ Mean mark 30%.
`text(route out of Dovenest and return home without)`
`text(going through another suburb or turning back.)`
NETWORKS, FUR1 2010 VCAA 4 MC
A board game consists of nine labelled squares as shown.
A player must start at square `J` and, moving one square at a time, aim to finish at square `R`.
Each move may only be to the right one square or down one square.
A player who lands on square `N` must stay there and cannot move again.
A player can only stop moving when they reach `N` or `R`.
A digraph that shows all the possible moves that a player could make to reach `N` or `R` from `J` is
NETWORKS, FUR1 2011 VCAA 3-4 MC
The map of Australia shows the six states, the Northern Territory and the Australian Capital Territory (ACT).
In the network diagram below, each of the vertices `A` to `H` represents one of the states or territories shown on the map of Australia. The edges represent a border shared between two states or between a state and a territory.
Part 1
In the network diagram, the order of the vertex that represents the Australian Capital Territory (ACT) is
A. `0`
B. `1`
C. `2`
D. `3`
E. `4`
Part 2
In the network diagram, Queensland is represented by
A. vertex A.
B. vertex B.
C. vertex C.
D. vertex D.
E. vertex E.
NETWORKS, FUR1 2013 VCAA 6 MC
The map above shows the road connections between three towns, `P, Q\ text(and)\ R`.
The graph that could be used to model these road connections is
NETWORKS, FUR1 2015 VCAA 6 MC
The map below shows all road connections between five towns, `U`, `V`, `W`, `X` and `Y`.
A graph, shown below, was constructed to represent this map.
A mistake has been made in constructing this graph.
This mistake can be corrected by
A. drawing another edge between `V` and `W`.
B. drawing a loop at `W`.
C. removing the loop at `V`.
D. removing one edge between `U` and `V`.
E. removing one edge between `X` and `V`.
NETWORKS, FUR2 2008 VCAA 2
Four children, James, Dante, Tahlia and Chanel each live in a different town.
The following is a map of the roads that link the four towns, `A`, `B`, `C` and `D`.
- How many different ways may a vehicle travel from town `A` to town `D` without travelling along any road more than once? (1 mark)
--- 5 WORK AREA LINES (style=lined) ---
James’ father has begun to draw a network diagram that represents all the routes between the four towns on the map. This is shown below.
In this network, vertices represent towns and edges represent routes between tow
- i. One more edge needs to be added to complete this network. Draw in this edge clearly on the diagram above. (1 mark)
--- 0 WORK AREA LINES (style=lined) ---
- ii. With reference to the network diagram, explain why a motorist at `A` could not drive each of these routes once only and arrive back at `A`. (1 mark)
--- 3 WORK AREA LINES (style=lined) ---
Show Answers Only
- `7`
- i.
b.ii. `text(See worked solution)`
Show Worked Solution
a. `text(Let the two unnamed intersections be)\ T_1\ text{(top) and}\ T_2.`
`text(The possible paths are:)`
♦♦ Exact data unavailable but “few students” answered this question correctly.
`ACD, ACT_2BD, ACT_2T_1BD, AT_1T_2CD,`
`AT_1T_2BD, AT_1BD, AT_1,BT_2CD.`
`:. 7\ text(different ways from)\ A\ text(to)\ D.`
| b.i. | |
b.ii. `text(Driving each route once and arriving back at)`
MARKER’S COMMENT: Be specific! Note that “an Eulerian circuit requires all vertices of an even degree” did not gain a mark here.
`A\ text(requires an Eulerian circuit where all)`
`text(vertices must be an even degree.)`
`text(The vertices at)\ C\ text(and)\ B\ text(are odd.)`
`:.\ text(No Eulerian circuit exists.)`