Networks activity 5
5. Create your own network that attempts to satisfy the priorities of the four centres. Explain how your network meets or fails to meet the requirements.
1) shortest path A to I
So A is told that the shortest distance between A and I is 30,000 km. You must state two other paths as evidence of your choice for Achieved or use Dijkstra's Algorithm for Merit Excellence.
2) maximum spanning tree scenic value
Use Kruskal's Algorithm and start with largest value first, don't make any circuits or "loops".
excellence component by describing the method chosen
Number of paths needed = number of nodes - 1
10 - 1 = 9 paths.
For a maximum spanning tree we start with the largest value. If there are more the same, take one at random. Colour and write the value of the path on the network diagram. Choose the next largest number, if it makes a circuit, reject it. If not accept it. Do this until you have all 9 paths recorded on the diagram. In this example there were no circuits made, so no need to reject a path.
10 - 1 = 9 paths.
For a maximum spanning tree we start with the largest value. If there are more the same, take one at random. Colour and write the value of the path on the network diagram. Choose the next largest number, if it makes a circuit, reject it. If not accept it. Do this until you have all 9 paths recorded on the diagram. In this example there were no circuits made, so no need to reject a path.
3) traversability
For a network to be traversable it must have zero or 2 odd nodes. If there happens to be two odd nodes (as in this case) then it is possible to travel from one node to the other node and vice versa but you cant go from one node and come back to the same node.
4) minimum spanning tree for cost
Use Kruskal's Algorithm starting at the lowest value, choose another path if a circuit is made, choosing the smallest value.