Directed Graphs
Weighted Graphs
Optimal Paths & Circuits
100
Determine d(A,B) in the graph below.
d(A, B) = 3
100
Determine the length of circuit MPNLM in the graph below. 
4
100
Determine the path of minimum value from vertex L to vertex J in the graph below.
LKHIJ / 8
200
Identify a simple circuit of length 4 in the graph below.
NOPQN or OPQNO or PQNOP or QNOPQ
200
Determine the value of path NMPNL in the graph below.
24
200
Determine the path of minimal value from vertex Q to vertex R in the graph below.
QOMPR / 10
300
Name an edge that would need to be added to the graph below to create an Euler circuit.
JK
300
The graph below shows the various cycling paths. A cyclist travels from stops F to T; passing through stops R and L on the way (FRLT). Determine the number of paths this cyclist traveled along this route.
3 paths
300
The graph below shows the roads connecting several schools that have competing sports teams. The weights represent the length of each road in km. Determine the minimum distance for a team from vertex R to travel to vertex W.
9km
400
A cardio circuit at the gym has the following stations. Determine the cardio routine (from W to C) that participants can complete the fastest (state the path not the time).
WA1N1C
400
The graph below shows the streets Antney likes to run around her neighbourhood. The values represent the length of each street, in km. Taking the route of TRUQRUS, Antney runs for a total of 18km. Determine the length of road RU, in km.
2km
400
The graph represents a race track, the vertices represent checkpoints, participants may start and end at any checkpoint but may not pass any point more than once. Determine the maximum distance a participant could run to complete this race.
495 m
500
There are several hiking paths that leave from the base (B) of a mountain and end at the peak (P). Determine the minimum distance (find the actual distance) a hiker could travel between the base (B) and peak (P).
640m
500
The graph below shows several streets in a county, with the weights representing the length of each street in km. The company hired by the county association charges $145 per km to clean the streets. Determine the total cost the association will pay to have the path HFDEG streets cleaned.
$3,480
500
Amy starts at vertex S and must go over each edge exactly once with before returning to vertex S. Find the minimum total distance Amy will cover.
332m