Networks

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 would normally represent the distance that you have to travel along that road.  Figure 1 shows such a network.

Figure 1: An example of a network. Roads connecting towns in southern England

Figure 1: An example of a network. Roads connecting 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.

There are two applications of networks that are covered in D1. These are:

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

Post a Comment

You must be logged in to post a comment.