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.i. \(\text{The bakery}\) 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}
Networks, GEN2 2023 VCAA 13
The state \(A\) has nine landmarks, \(G, H, I, J, K, L, M, N\) and \(O\).
The edges on the graph represent the roads between the landmarks.
The numbers on each edge represent the length, in kilometres, along each road.
Three friends, Eden, Reynold and Shyla, meet at landmark \(G\).
- Eden would like to visit landmark \(M\).
- What is the minimum distance Eden could travel from \(G\) to \(M\) ? (1 mark)
--- 1 WORK AREA LINES (style=lined) ---
- Reynold would like to visit all the landmarks and return to \(G\).
- Write down a route that Reynold could follow to minimise the total distance travelled. (1 mark)
--- 1 WORK AREA LINES (style=lined) ---
- Shyla would like to travel along all the roads.
- To complete this journey in the minimum distance, she will travel along two roads twice.
- Shyla will leave from landmark \(G\) but end at a different landmark.
- Complete the following by filling in the boxes provided.
- The two roads that will be travelled along twice are the roads between: (1 mark)
--- 0 WORK AREA LINES (style=lined) ---
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)
- What is the degree of vertex `E`? (1 mark)
- 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)
ii. What is the mathematical term for such a journey? (1 mark)
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, FUR1 2021 VCAA 5 MC
Consider the following five statements about the graph above:
-
- The graph is planar.
- The graph contains a cycle.
- The graph contains a bridge.
- The graph contains an Eulerian trail.
- The graph contains a Hamiltonian path.
How many of these statements are true?
- 1
- 2
- 3
- 4
- 5
NETWORKS, FUR2 2020 VCAA 3
A local fitness park has 10 exercise stations: `M` to `V`.
The edges on the graph below represent the tracks between the exercise stations.
The number on each edge represents the length, in kilometres, of each track.
The Sunny Coast cricket coach designs three different training programs, all starting at exercise station `S`.
| Training program number |
Training details | |
| 1 | The team must run to exercise station `O`. | |
| 2 | The team must run along all tracks just once. | |
| 3 | The team must visit each exercise station and return to exercise station `S`. |
- What is the shortest distance, in kilometres, covered in training program 1? (1 mark)
- i. What mathematical term is used to describe training program 2? (1 mark)
- ii. At which exercise station would training program 2 finish? (1 mark)
- To complete training program 3 in the minimum distance, one track will need to be repeated.
Complete the following sentence by filling in the boxes provided. (1 mark)
This track is between exercise station and exercise station
NETWORKS, FUR1 2020 VCAA 2 MC
Consider the graph below.
Which one of the following is not a Hamiltonian cycle for this graph?
- `ABCDFEGA`
- `BAGEFDCB`
- `CDFEGABC`
- `DCBAGFED`
- `EGABCDFE`
NETWORKS, FUR2 2019 VCAA 1
Fencedale High School has six buildings. The network below shows these buildings represented by vertices. The edges of the network represent the paths between the buildings.
- Which building in the school can be reached directly from all other buildings? (1 mark)
- A school tour is to start and finish at the office, visiting each building only once
- What is the mathematical term for this route? (1 mark)
- Draw in a possible route for this school tour on the diagram below. (1 mark)
Show Worked Solution
a. `text(Office)`
b.i. `text(Hamiltonian cycle)`
`text{(note a Hamiltonian path does not start and finish}`
`text{at the same vertex.)}`
b.ii. `text(One of many solutions:)`
NETWORKS, FUR2 2016 VCAA 2
The suburb of Alooma has a skateboard park with seven ramps.
The ramps are shown as vertices `T`, `U`, `V`, `W`, `X`, `Y` and `Z` on the graph below.
The tracks between ramps `U` and `V` and between ramps `W` and `X` are rough, as shown on the graph above.
- Nathan begins skating at ramp `W` and follows an Eulerian trail.
At which ramp does Nathan finish? (1 mark)
- Zoe begins skating at ramp `X` and follows a Hamiltonian path.
The path she chooses does not include the two rough tracks.
Write down a path that Zoe could take from start to finish. (1 mark)
- Birra can skate over any of the tracks, including the rough tracks.
He begins skating at ramp `X` and will complete a Hamiltonian cycle.
In how many ways could he do this? (1 mark)
NETWORKS, FUR1 2008 VCAA 3 MC
A Hamiltonian circuit for the graph above is
A. `K J I H G L F E D K`
B. `D K L I J H G F E D`
C. `D E F G H I J K D`
D. `J I K D L H G F E`
E. `G H I L K J I L D E F G `
NETWORKS, FUR1 2006 VCAA 3 MC
Which one of the following statements is true regarding the network above?
A. `ABCDEFG` is a Hamiltonian circuit.
B. Only one Hamiltonian path exists.
C. `CBAGFEDC` is an Eulerian circuit.
D. At least two Eulerian paths exist.
E. There are no circuits.
NETWORKS, FUR1 2011 VCAA 6 MC
A store manager is directly in charge of five department managers.
Each department manager is directly in charge of six sales people in their department.
This staffing structure could be represented graphically by
A. a tree.
B. a circuit.
C. an Euler path.
D. a Hamiltonian path.
E. a complete graph.
NETWORKS, FUR1 2012 VCAA 2 MC
The number of Hamiltonian circuits involving all five vertices in the graph above is
A. `0`
B. `1`
C. `2`
D. `3`
E. `4`
NETWORKS, FUR2 2007 VCAA 2
The estate has large open parklands that contain seven large trees.
The trees are denoted as vertices `A` to `G` on the network diagram below.
Walking paths link the trees as shown.
The numbers on the edges represent the lengths of the paths in metres.
- Determine the sum of the degrees of the vertices of this network. (1 mark)
- One day Jamie decides to go for a walk that will take him along each of the paths between the trees.
He wishes to walk the minimum possible distance.
- State a vertex at which Jamie could begin his walk. (1 mark)
- Determine the total distance, in metres, that Jamie will walk. (1 mark)
Michelle is currently at `F`.
She wishes to follow a route that can be described as the shortest Hamiltonian circuit.
- Write down a route that Michelle can take. (1 mark)
NETWORKS, FUR1 2014 VCAA 1 MC
The graph below shows the roads connecting four towns: Kelly, Lindon, Milton and Nate.
A bus starts at Kelly, travels through Nate and Lindon, then stops when it reaches Milton.
The mathematical term for this route is
A. a loop.
B. an Eulerian path.
C. an Eulerian circuit.
D. a Hamiltonian path.
E. a Hamiltonian circuit.
NETWORKS, FUR2 2009 VCAA 3
The city of Robville contains eight landmarks denoted as vertices `N` to `U` on the network diagram below. The edges on this network represent the roads that link the eight landmarks.
- Write down the degree of vertex `U`. (1 mark)
- Steven wants to visit each landmark, but drive along each road only once. He will begin his journey at landmark `N`.
- At which landmark must he finish his journey? (1 mark)
- Regardless of which route Steven decides to take, how many of the landmarks (including those at the start and finish) will he see on exactly two occasions? (1 mark)
- Cathy decides to visit each landmark only once.
- Suppose she starts at `S`, then visits `R` and finishes at `T`.
Write down the order Cathy will visit the landmarks. (1 mark)
- Suppose Cathy starts at `S`, then visits `R` but does not finish at `T`.
List three different ways that she can visit the landmarks. (1 mark)
- Suppose she starts at `S`, then visits `R` and finishes at `T`.
NETWORKS, FUR2 2010 VCAA 2
The diagram below shows a network of tracks (represented by edges) between checkpoints (represented by vertices) in a short-distance running course. The numbers on the edges indicate the time, in minutes, a team would take to run along each track.
Another challenge requires teams to run from checkpoint `X` to checkpoint `Y` using these tracks.
- What would be the shortest possible time for a team to run from checkpoint `X` to checkpoint `Y`? (1 mark)
- Teams are required to follow a route from checkpoint `X` to checkpoint `Y` that passes through every checkpoint once only.
- What mathematical term is used to describe such a route? (1 mark)
- On the network diagram below, draw in the route from checkpoint `X` to checkpoint `Y` that passes through every checkpoint once only. (1 mark)
Show Answers Only
- `11\ text(minutes)`
-
- `text(Hamiltonian path)`
-
Show Worked Solution
a. `4 + 3 + 4 = 11\ text(minutes)`
b.i. `text(Hamiltonian path)`
| b.ii. |  |
NETWORKS, FUR2 2011 VCAA 1
Aden, Bredon, Carrie, Dunlop, Enwin and Farnham are six towns.
The network shows the road connections and distances between these towns in kilometres.
- In kilometres, what is the shortest distance between Farnham and Carrie? (1 mark)
- How many different ways are there to travel from Farnham to Carrie without passing through any town more than once? (1 mark)
An engineer plans to inspect all of the roads in this network.
He will start at Dunlop and inspect each road only once.
- At which town will the inspection finish? (1 mark)
Another engineer decides to start and finish her road inspection at Dunlop.
If an assistant inspects two of the roads, this engineer can inspect the remaining six roads and visit each of the other five towns only once.
- How many kilometres of road will the assistant need to inspect? (1 mark)
NETWORKS, FUR2 2013 VCAA 1
The vertices in the network diagram below show the entrance to a wildlife park and six picnic areas in the park: `P1`, `P2`, `P3`, `P4`, `P5` and `P6`.
The numbers on the edges represent the lengths, in metres, of the roads joining these locations.
- In this graph, what is the degree of the vertex at the entrance to the wildlife park? (1 mark)
- What is the shortest distance, in metres, from the entrance to picnic area `P3`? (1 mark)
- A park ranger starts at the entrance and drives along every road in the park once.
- At which picnic area will the park ranger finish? (1 mark)
- What mathematical term is used to describe the route the park ranger takes? (1 mark)
- A park cleaner follows a route that starts at the entrance and passes through each picnic area once, ending at picnic area `P1`.
Write down the order in which the park cleaner will visit the six picnic areas. (1 mark)
NETWORKS, FUR2 2014 VCAA 3
The diagram below shows a network of train lines between five towns: Attard, Bower, Clement, Derrin and Eden.
The numbers indicate the distances, in kilometres, that are travelled by train between connected towns.
Charlie followed an Eulerian path through this network of train lines.
-
- Write down the names of the towns at the start and at the end of Charlie’s path. (1 mark)
- What distance did he travel? (1 mark)
Brianna will follow a Hamiltonian path from Bower to Attard.
- What is the shortest distance that she can travel? (1 mark)
The train line between Derrin and Eden will be removed. If one other train line is removed from the network, Andrew would be able to follow an Eulerian circuit through the network of train lines.
- Which other train line should be removed?
In the boxes below, write down the pair of towns that this train line connects. (1 mark)
NETWORKS, FUR2 2015 VCAA 2
The factory supplies groceries to stores in five towns, `Q`, `R`, `S`, `T` and `U`, represented by vertices on the graph below.
The edges of the graph represent roads that connect the towns and the factory.
The numbers on the edges indicate the distance, in kilometres, along the roads.
Vehicles may only travel along the road between towns `S` and `Q` in the direction of the arrow due to temporary roadworks.
Each day, a van must deliver groceries from the factory to the five towns.
The first delivery must be to town `T`, after which the van will continue on to the other four towns before returning to the factory.
-
- The shortest possible circuit from the factory for this delivery run, starting with town `T`, is not Hamiltonian.
Complete the order in which these deliveries would follow this shortest possible circuit. (1 mark)
factory – `T` – ___________________________ – factory
- With reference to the town names in your answer to part (a)(i), explain why this shortest circuit is not a Hamiltonian circuit. (1 mark)
- The shortest possible circuit from the factory for this delivery run, starting with town `T`, is not Hamiltonian.
- Determine the length, in kilometres, of a delivery run that follows a Hamiltonian circuit from the factory to these stores if the first delivery is to town `T`. (1 mark)