A network is a graph in which each edge is assigned a number.
Perhaps the easiest way to think of this is to imagine a graph showing the main roads between towns. The number on the edges might represent the distance between the towns connected by that road, or the time taken to travel between those towns.
The numbers that correspond to each edge are called weights.
There are several applications of networks that are covered in D1. These are:
- Minimum connector or minimum spanning tree - The tree that connects all of the vertices in the set with the minimum weight when all included edges are summed.
- Finding the Shortest Path between two vertices in a network- The shortest path that connects any two vertices in a set.
- Critical Path Analysis – Finding the minimum time needed to complete a project.
- Chinese Postman Problem or Route Inspection Problem – The problem of visiting traversing every arc in a network while minimising the distance travelled. Some arcs may have to be traversed twice in order that every arc is traversed.
- Travelling Salesman Problem – The problem of minimising the sum of the weights of the arcs traversed travelled while visiting each vertex once.