- #1
CheeseyChips
- 3
- 0
Have to do this question fairly soon in an exam. This is pretty much the exact same question that will be on it.
What sort of maths is this and how the hell do I do it??!? I don't have any notes on it.
-----------
The following network (Figure 1 below) represents the road system in the town A-Town, with streets being edges and street junctions being vertices. The number on each street represents the length of the street in metres. Traffic can travel in either direction along any street: there are no one-way streets in the town.
1. Use an appropriate algorithm to find, for each vertex, the shortest path (and its length) from vertex 1 to that vertex. Include workings with your solution.
• Draw the resulting shortest path spanning tree rooted at vertex 1.
• Which are the vertices in the shortest path between vertices 1 and 13?
Discuss other examples of where a model/problem like this could arise.
2. The Post Office is located at the junction marked 1 in Figure 1. Postman Pat is starting on his round. He wants to start from the Post Office, deliver the post along each street, and return to the Post Office at the end of the round. What tour should Pat take, and what is its length? Use an appropriate graph algorithm to find your answer. [Hint: your work in Question 1 will be useful here.]
3. The A-Town town council wish to resurface certain streets in the town, so that it will be possible to get from any junction to any other junction using only the newly-resurfaced streets. Using an appropriate graph algorithm, find which streets should be resurfaced so as to minimise the total length of street resurfaced.
--------------------------
What sort of maths is this and how the hell do I do it??!? I don't have any notes on it.
-----------
The following network (Figure 1 below) represents the road system in the town A-Town, with streets being edges and street junctions being vertices. The number on each street represents the length of the street in metres. Traffic can travel in either direction along any street: there are no one-way streets in the town.
1. Use an appropriate algorithm to find, for each vertex, the shortest path (and its length) from vertex 1 to that vertex. Include workings with your solution.
• Draw the resulting shortest path spanning tree rooted at vertex 1.
• Which are the vertices in the shortest path between vertices 1 and 13?
Discuss other examples of where a model/problem like this could arise.
2. The Post Office is located at the junction marked 1 in Figure 1. Postman Pat is starting on his round. He wants to start from the Post Office, deliver the post along each street, and return to the Post Office at the end of the round. What tour should Pat take, and what is its length? Use an appropriate graph algorithm to find your answer. [Hint: your work in Question 1 will be useful here.]
3. The A-Town town council wish to resurface certain streets in the town, so that it will be possible to get from any junction to any other junction using only the newly-resurfaced streets. Using an appropriate graph algorithm, find which streets should be resurfaced so as to minimise the total length of street resurfaced.
--------------------------