State the definition of a path.
For each of the following graphs, state a valid path:
Determine the number of unique paths from B \text{ to } D without passing over the same vertex twice.
Determine whether the following are valid paths in the given network:
A, E, C
A, D, C
B, A, E
E, C, B
E, D, B
Give two examples of valid paths in the following networks:
A private school bus is to pick up students from a certain area. The following map shows the routes connecting the students' houses:
The bus driver wants to save as much time as possible on his route. If he starts his route at vertex D, what is the shortest path that visits each house exactly once?
The given map shows all possible routes in Mohamad's town. Mohamad travels from his home to his friend's house on a daily basis.
If Mohamad's house is vertex C, and his friend's house is vertex I, determine the shortest path between the two houses.
A group is organizing a tour for the elderly in a park, ending with a picnic. The given graph displays the map of the park:
Calculate the path which gives the shortest distance from the start of the park at vertex A, to the picnic area at vertex J.
A particular supplier delivers goods to a supermarket chain in five towns. The following map displays the routes between the supplier (vertex E) and the five towns (in kilometres):
The supplier needs to make a quick delivery to the supermarket in town B. What is the shortest path from E to B?
Draw the minimum spanning tree for this network.
Does the shortest path between E and B lie on the minimum spanning tree?
A courier is to make multiple pick-ups from several stores. The following map displays the routes between the stores (in kilometres):
Store D needs immediate pick up and must be visited first. If the courier is currently at store F, what is the shortest path that visits store D first and then every other store exactly once after that?
If instead the courier did not need to visit store D first, what would be the shortest path starting at F that visits every store exactly once?
Determine the minimum spanning tree for this network.
Which of the shortest paths from parts (a) and (b) lie on the minimum spanning tree?
