NETWORKS PRACTICE 2
2024
1) Find the shortest path between nodes A and I. State the order of nodes chosen.
This can be done by guess and check.
2) Can the whole of this set of paths be travelled going on each path once and only once? Give a full explanation for your answer.
Notes reminder:
A traversable network is one that can be drawn without lifting the pen from the paper and without retracing the same path (arc). The rules that make a network traversable are:
A traversable network is one that can be drawn without lifting the pen from the paper and without retracing the same path (arc). The rules that make a network traversable are:
- if all nodes are even order, we can start anywhere (and finish anywhere including back at the start node, which is called an Euler circuit).
- if there are EXACTLY two nodes with an odd order (all others even), we must start at one odd node (and finish at the other odd node). This is called an Euler path.
3) What is the minimum spanning network for this and what is the distance of span required?
We will use Kruskal's Algorithm to solve this network problem and take it one step at a time. Firstly the number of paths we need is found from a simple formula which states
The number of paths = number of nodes - 1
= 9 -1
= 8
Now write out 8 spaces where we will in turn allocate each path starting from the smallest distance to the largest distance. If one pathway creates a circuit, remove it.
"Looking at my highlighted network and using Kruskal's algorithm, I found the least distance that connects all 9 locations is 79,000 km".
4) What is the maximum spanning network for this and what is the distance span required?
maximum spanning tree
"Looking at my highlighted network and using Kruskal's algorithm, I found the maximum distance that connects all 9 locations is 105,000 km".