Networks

A network is a graph in which one or more edges is assigned a number, called its weight.

Perhaps the easiest way to think of this is to imagine a graph showing the main roads between towns. The number on the edges would normally represent the distance that you have to travel along that road. Figure 1 shows such a network.

Figure 1. Network diagram of road connections between major towns in southern England.
Figure 1. Network diagram of road connections between major towns in southern England.

This graph of roads connecting towns in southern England has had the distances in miles added to the edges that represent the routes. This makes the graph a network.

The numbers that correspond to each edge are called weights.

The discrete maths that is included at A Level contains two main applications of networks. These are:

  1. Minimum connector. The tree that connects all of the vertices in the set with the minimum weight when all included edges are summed.
  2. Shortest path The shortest path that connects any two vertices in the set.

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.