Auckland Sports College
|
"Moving Forward Together"
|
|
Networks
This is a 2 Credit, Level 2 Achievement standard.
|
The topics in Networks are
|
|
A six minute youtube summary of the standard is here .
Most of the figures on this page are taken from the "snedmaths" website. Mr Sneddon is head of maths at St Kents.
Nodes, Edges, Paths
In this course we think of networks as diagrams that represent maps. They consist of nodes, which represent the places (e.g cities) and edges which represent the connections (e.g roads) between nodes (places). The edges may have a "weight" (e.g the distance between cities)
|
This is a network diagram of 5 towns (the nodes or vertices R, P, O, T, L) and the roads (edges) which connect them. The distance between each town is the weight of the edge (for example the distance betwwen R and L is 212) There is no road which connects R and O directly. To get from R to O you have to go through P, or maybe L and T A path is a way to get from one node to another. R-P-O is a path from R to O R to P to L forms a circuit or loop (a closed path from a node back to itself) within the network. So does P-L-T-O and R-L-T-O-P The degree of a node is the number of edges attached to it. Nodes are 'odd' if they have an odd number of edges and 'even' if they have an even number of edges. L and P are odd nodes of degree 3. R, T, and O are even nodes of degree 2. This network is 'connected'. There are no nodes of zero degree (i.e every node has at least one edge attached to it). |
|
Distance Table
A distance table is a table where the weights of the edges are listed.If there is no edge joing the two nodes there is a '-' in that cell of the table.The tabe below lists the distances by road between various towns
The distance between Hamilton and Te Awamutu is 29.
In your assessment you might be given a network diagram and asked to construct a distance table. Or you could be given a distance diagram and a node diagram and asked to construct the network.
Here is an example where you are given the distance table and the node diagram
Here is the network diagram
Shortest Path
In the assessment you will probably be asked to find the shortest path between 2 nodes. To do this find the distance of 3 or 4 paths that might be the shortest, and choose the shortest from them. In the example we have been using, if you are asked to find the shortest path between R and O you might tryR-P-O = 136 + 127 = 263
R-L-T-O = 212 + 99 + 124 = 435
and conclude that thee shortest path between R and O is R-P-O with a distance of 263.
Traversability
A network is traversable if there is a path through it that uses every edge once. So, in the example we have been using one 'traverse' is L-R-P-L-T-O-PNetworks that only have even nodes are traversable. You can start at any node and finish at that node.
Networks that have two odd nodes are traversable. You start at one odd node and finish at the other.
So, networks are traversable if they have no odd nodes or two odd nodes.
Minimum Spanning Tree
A tree is a connected network with no circuits.
This is a tree with 6 nodes and 5 edges
A spanning tree for a network is a tree that uses all of the nodes of the network, and some of the edges. It's a collection of just enough edges that there is a path from any node to any other node.
A spanning tree with the minimum total weight is called a minimum spanning tree.
In your assessment you are going to be asked to find a minimum spanning tree. There are two ways of doing this
Kruskal's Algorithm (the name is not important)
- 1. Find the smallest weight edge in the network
- 2. Add this edge to the minimum spanning tree unless this would create a circuit. If it would create a circuit discard this edge
- 3. While the network is not a spanning tree return to step 1
- Discard all the edges that are not part of the minimum spanning tree
Circuit-Delete Algorithm (the name is not important)
- 1. Find a circuit in the network
- 2. Remove the edge in the circuit with the largest weight
- 3. If there are any circuits left in the network return to step 1