NETWORKS ACTIVITY 6
2023
updated version
1)shortest path between b and g
Shortest path between B and G. I used trial and error to find the shortest path between B and G.
My chosen path is B-I-H-G which = 30km.
Two other paths could be
B-F-H-G = 33km
and B-A-D-G = 37km but these are longer distances.
My chosen path is B-I-H-G which = 30km.
Two other paths could be
B-F-H-G = 33km
and B-A-D-G = 37km but these are longer distances.
2) maximum spanning tree for scenic value.
Number of paths needed = number of nodes - 1
10 - 1 = 9 paths.
BF/9 + DC/8 +DG/8 + EG/8 + EF/7 + IF/7 + IJ/7 + BI/6 + HJ/6 (makes a circuit) + AD/5
= 65 Scenic beauty points.
10 - 1 = 9 paths.
BF/9 + DC/8 +DG/8 + EG/8 + EF/7 + IF/7 + IJ/7 + BI/6 + HJ/6 (makes a circuit) + AD/5
= 65 Scenic beauty points.
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. I rejected the path from H to J because it made a circuit.
3) Traversability
For a network to be traversable it must have zero or 2 odd nodes. If there happens to be two odd nodes 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. In this case there are 6 odd nodes so it is not traversable.
4) find the least expensive network that connects all 10 locations
(Minimum spanning tree)
Location J wants the least expensive network that connects all 10 locations. I will use Kruskal's Algorithm to create a minimum spanning tree for the network by selecting the smallest value (lowest cost) pathways first followed by the next smallest value without creating any circuit or loop.
Using Kruskal's Algorithm the least expensive network can be found.
Excellence
Excellence is obtained by describing the process of how you used Kruskol's Algorithm in determining the maximum spanning tree for scenic value.
Number of paths needed = number of nodes - 1
10 - 1 = 9
9 paths are needed.
Number of paths needed = number of nodes - 1
10 - 1 = 9
9 paths are needed.
So there are 65 scenic value points.
We start with the largest scenic value (if there are two, choose one at random) shade in the path, record it and choose the next highest number. If this path creates a circuit then reject it. If not, keep it and record it. Follow this procedure until all 9 paths are filled. I rejected a path from J to H because it completed a circuit.
We start with the largest scenic value (if there are two, choose one at random) shade in the path, record it and choose the next highest number. If this path creates a circuit then reject it. If not, keep it and record it. Follow this procedure until all 9 paths are filled. I rejected a path from J to H because it completed a circuit.