networks 7
jack and his friend
To speed up things a little, all distances have been added to the diagram for you. Jack lives in a village (A) and needs to go to the shipping port located at I to pick up a friend who is on a day trip from the mainland.
1) Find the shortest way that Jack can get to the port.
2) Jack wants to show his visitor as many sights as possible without repeating a road starting and finishing at the port. If that's not possible he can travel down a road more than once. Suggest a route for this.
3) The roads operate on a toll system linked to distance, for example a 6 km road costs $6, a 10 km road cost $10 etc. Jack is really budget strapped. Suggest a route he could take so that he can take his friend through every village, starting from the port. You do not have to calculate the cost of any route.
1) Find the shortest way that Jack can get to the port.
2) Jack wants to show his visitor as many sights as possible without repeating a road starting and finishing at the port. If that's not possible he can travel down a road more than once. Suggest a route for this.
3) The roads operate on a toll system linked to distance, for example a 6 km road costs $6, a 10 km road cost $10 etc. Jack is really budget strapped. Suggest a route he could take so that he can take his friend through every village, starting from the port. You do not have to calculate the cost of any route.
4) Finally, Jack collects another friend from the port the following week. Under lock down it has been necessary to implement some quarantine measures and police have set up roads blocks around the area. E to G and B to H and B to J are blocked. Also A to B and D to B are one way with no permitted return.
Starting from the port, Jack would like to visit as many villages as possible. Investigate his options.
possible solutions
1) Find the shortest way that Jack can get to the port.
He needs to travel from village A to the port (I) through villages E, G and F.
Dijkstra's Algorith shows this to be 30km.
He needs to travel from village A to the port (I) through villages E, G and F.
Dijkstra's Algorith shows this to be 30km.
2) Jack wants to show his visitor as many sights as possible without repeating a road starting and finishing at the port. If that's not possible he can travel down a road more than once. Suggest a route for this.
There are many possibilities. The network is traversable because there are two odd nodes, villages F and J. But to travel along each road only once they would need to start at either odd node. So if they start at village F they would finish at village J and vice versa. Completing the network and getting back to the port means crossing 2 roads twice, these are the roads that lead to villages F and J. Shown below is just one way of traveling.
There are many possibilities. The network is traversable because there are two odd nodes, villages F and J. But to travel along each road only once they would need to start at either odd node. So if they start at village F they would finish at village J and vice versa. Completing the network and getting back to the port means crossing 2 roads twice, these are the roads that lead to villages F and J. Shown below is just one way of traveling.
3) The roads operate on a toll system linked to distance, for example a 6 km road costs $6, a 10 km road cost $10 etc. Jack is really budget strapped. Suggest a route he could take so that he can take his friend through every village. You do not have to calculate the cost of any route.
The hint here is Jack is budget strapped so he should travel the roads which will cost him the least amount of money in toll charges. So this is a minimum spanning tree which you should solve with Kruskal's Algorithm.
FI/7 + BD/3 + HJ/3 + AD/5 + AE/6 + HF/7 + EG/8 + CH/8 + GF/9
This adds to $56 which is the collective value of the tolls. In reality they would need to travel down the roads twice which gives a toll value of $112. There were two paths of 9 km each and only one was needed. Replacing one with the other gives the same answer, $112. Possible network diagram below. You don't have to calculate the cost of the trip in toll charges but it would be a good idea to follow the logic.
The hint here is Jack is budget strapped so he should travel the roads which will cost him the least amount of money in toll charges. So this is a minimum spanning tree which you should solve with Kruskal's Algorithm.
FI/7 + BD/3 + HJ/3 + AD/5 + AE/6 + HF/7 + EG/8 + CH/8 + GF/9
This adds to $56 which is the collective value of the tolls. In reality they would need to travel down the roads twice which gives a toll value of $112. There were two paths of 9 km each and only one was needed. Replacing one with the other gives the same answer, $112. Possible network diagram below. You don't have to calculate the cost of the trip in toll charges but it would be a good idea to follow the logic.
4) Finally, Jack collects another friend from the port the following week. Under lock down it has been necessary to implement some quarantine measures and police have set up roads blocks around the area. E to G and B to H and B to J are blocked. Also A to B and D to B are one way with no permitted return.
Starting from the port, Jack would like to visit as many villages as possible. Investigate his options.
You can't go to village B as it's one way and you need to take your friend back to the port. Most of the road distances traveled are doubled (very important statement) and only the roads from village H back to the port via village J is travelled once.