Networks and Road Maps, Part I

In the last section, you saw how mathematicians create new ideas byremoving requirements from old ones. In this section, we'll create a new idea by adding onto an old one. Not all connections are created equal. In some situations, electrical circuits, for example, we need a way to assign values to the connections.

What You Should Learn

  • How a graph is transformed into a network by adding a set of numbers.
  • Real world situations that are modeled by networks.
circuit board

A roadmap, with travel distances, is a real world example of a network.

A network is a graph or digraph that also has a function that maps the edges onto the set of real numbers. A network derived from a graph is called an undirected network. A network derived from a digraph is called a directed network. A signed graph is a special case of an undirected network where the functional values are either +1 or -1.

All that business about "a function that maps ..." just means that each edge is assigned a number.

Let's take a concrete example and look at it from both perspectives.

Let V = { v1, v2, v3, v4, v5 } and let R = { (v4, v2), (v3, v4), (v3, v1), (v3, v5), (v5, v3) } be a digraph. (This is the same graph that we looked at in the last section.)

We can turn this into a graph by assigning a value to each of the edges. f = { (v4 v2, -3.5), (v3 v4, 4), (v3 v1, 5), (v3 v5, 2), (v5 v3, -2) }. Notice that the values can be positive, negative, decimals, etc. I could also have used square roots, multiples of π or any other number that I needed.

The picture below illustrates the network visually. The drawing is identical to the one from the previous section except I added numbers to each segment to indicate their values.

graph 4

Our street map example from the previous section can be quickly converted to a network by assigning to the piece of road between two intersections the distance between the intersections. We'll look at this more in the exercises and come back to it again in a later section as part of a classic example called the traveling salesman problem.

Networks and Road Maps, Part II >><< Digraphs and One Way Streets, Exercises