A-level Mathematics/MEI/D1/Networks

From Wikibooks, open books for an open world
< A-level Mathematics‎ | MEI‎ | D1
Jump to: navigation, search

Introduction[edit]

Networks are weighted graphs, their edges have associated weights with them. Networks are useful for modelling geographical problems (though they have many other uses).

Network

Networks have a walk called the minimum spanning tree which is the shortest walk that connects every node in the network via edges. There are two algorithms for producing the minimal spanning tree: Kruskal's algorithm and Prim's algorithm, by the end of this page you should be able to use both algorithms in graphical form and Prim's algorithm in tabular form.

Finally you should also be able to use Dijkstra's algorithm to find the shortest route between two points.

Algorithms[edit]

Minimal spanning tree[edit]

Kruskal's algorithm[edit]


  1. Pick the shortest edge of the network.
  2. Pick the next shortest edge of the network that doesn't link nodes between which a path has already been established.
  3. Repeat 2, until n-1 edges have been selected (where n is the number of nodes in the network).

Here's an example on Wikipedia: Kruskal's algorithm example.

Prim's algorithm[edit]


Graphical approach[edit]
  1. Pick an arbitrary node.
  2. Connect that node to it's nearest node by an edge.
  3. Now connect the nearest node that isn't already connected to the walk you're forming.
  4. Repeat 3 until all nodes have been connected.

Example: Graphical run of Prim's algorithm.

Tabular approach[edit]

Networks can be represented in tabular form where distances are recorded between nodes.

  1. Select an arbitrary node X.
  2. Delete row X.
  3. Look for smallest value in column X, read which node it belongs to, this is your new node Y.
  4. Delete row Y.
  5. Look for smallest value in column X and Y, then goto 3, repeat until network is connected.

Example: | Tabular run of Prim's algorithm.

Shortest path[edit]

Dijkstra's algorithm[edit]


Permanent labels (P-labels) are depicted by a value contained in a box.

Temporary labels (T-labels) are depicted by a value with no box.

  1. Step 1
    1. Label start node S with a P-label of 0.
    2. For all nodes reachable from S, assign a T-label equal to their direct distances from S.
    3. Select the node with the smallest T-label value, make this a P-label, this label marks the shortest distance from S to that node
  2. Step 2
    1. Put a T-label on each node that can be reached directly from the node that has just been marked with a P-label. The T-label should be equal to the sum of the P-label and the direct distance from it. If there is an existing T-label at a node, it should be replaced if the new sum is smaller.
    2. Select the minimum T-label and make it permanent.
    3. If this labels the destination node continue, else repeat step 2.
  3. Step 3
    1. Trace back from the current node (the destination node) to the start node including any edge MN where (P-label of M) - (P-lalbel of N) = length of arc MN.

Example:

Find the shortest route between S and T using Dijkstra's algorithm.

Image Description
Dijkstra algorithm 1.svg Here's the initial graph.
Dijkstra algorithm 2.svg Start by labelling the start node with a P-label of zero.
Dijkstra algorithm 3.svg Mark the directly connected nodes with T-labels of their distances from the start node.
Dijkstra algorithm 4.svg Make the lowest T-label a P-label, then mark it's directly connected nodes with T-labels of their own.

Note: the T-label of Q has been cropped, it's 7

Dijkstra algorithm 5.svg Make the lowest T-label a P-label, mark it's directly connected connected nodes with T-labels of their own, here X's T-label has been relabelled as 4 as a shorted route has been found.
Dijkstra algorithm 6.svg Make the lowest T-label a P-label, mark it's directly connected connected nodes with T-labels of their own

Note: the T-label of V is cropped out, it's 6

Dijkstra algorithm 8.svg Make the lowest T-label a P-label, mark it's directly connected connected nodes with T-labels of their own
Dijkstra algorithm 9.svg Make the lowest T-label a P-label, mark it's directly connected connected nodes with T-labels of their own
Dijkstra algorithm 10.svg Make the lowest T-label a P-label, mark it's directly connected connected nodes with T-labels of their own
Dijkstra algorithm 11.svg Make the lowest T-label a P-label, mark it's directly connected connected nodes with T-labels of their own
Dijkstra algorithm 12.svg Make the lowest T-label a P-label, mark it's directly connected connected nodes with T-labels of their own
Dijkstra algorithm 13.svg Finally trace back from the current node (the destination node) to the start node including any edge MN where (P-label of M) - (P-lalbel of N) = length of arc MN.

Route, SUVWT is a shortest path, SPQRT also is a shortest path (but this wasn't chosen for the demonstration).