topic badge

11.01 Introduction to networks (Extension)

Lesson

What do roads, human ancestry, currency exchange, planning a wedding, and the internet have in common? They can all be represented with a mathematical object called a network. Studying networks allows us to gain insights into any system of objects, people, places or ideas that have connections between them.

You have seen networks before, all around you! We are now going to learn how to recognise them, represent them in a consistent way, then analyse them. But first, we need to start with the language of networks to introduce the key concepts.

Warning!

This subject is well known for using many different words to refer to the same thing. This reflects the rich history of the subject, and its accessibility - networks have been studied by people all over the world in many different ways, and nobody agrees on a standard way to talk about them.

The concepts are the most important thing to remember, much more than the name that we give it. We have included some alternate terminology alongside the terms that we will use.  

A vertex (or node) is the fundamental building block of a network and represents a single object or idea. It is drawn as a dot or circle. The plural of vertex is vertices.

An edge (or arc or link) is a line segment that begins and ends at a vertex. An edge represents a relationship between the objects or ideas that it links together, and the kind of relationship depends on the context.

On the left is a single vertex. On the right are two vertices with one edge between them.

On the left is a single vertex. On the right there are two vertices with one edge between them.

An edge must be drawn between exactly two vertices. Neither of these are valid edges:

An edge can’t connect at only one end, and can’t connect more than two vertices together.

A network (sometimes called a network graph, or just graph) is a collection of vertices with edges drawn between them.

Four different networks.

Let’s take a moment and notice a few things about the networks above:

  • Some edges have direction (they look like arrows), and some don’t
  • Sometimes a vertex is connected to itself by an edge
  • Sometimes vertices are connected to another vertex by more than one edge
  • One of the networks has numbered edges (weighted edges)

Here are three more networks - these have letters or words for each vertex:

Three more networks with extra detail.

Vertices in networks are often given vertex labels. These labels can be something specific such as the name of a person, city, or animal or it can be more abstract, like a capital letter. In the networks above, the first one has capital letters $A$A, $B$B, $C$C, $D$D and $E$E for labels, which is useful for pointing out a particular vertex to someone else. The other two networks have labels that tell us what is being represented.

 

Different kinds of edges and networks

Edges can be either directed or undirected.

  • Directed edges (sometimes called arcs) are represented by arrows and symbolise a one-way relationship.
  • Undirected edges are represented by lines and symbolise a two-way connection.

The first network has a directed edge, because sharks eat fish and not the other way around - a one-way relationship. The second network has an undirected edge, because France and Spain share a border - a two-way relationship.

If there are directed edges in the network, we call the network a directed network (or digraph). If there are no directed edges in a network, we call the network an undirected network. Look back through the networks you’ve seen so far - those with arrows are directed, and the rest are undirected.

What about if there's a mix - some arrowheads, some lines?

Edges in undirected networks represent two-way connections. If there are directed edges in a network, then one-way connections are possible. So we turn the lines representing two-way connections into two arrows, like this:

We can still express a two-way connection using directed edges, we just have to draw in an extra (directed) edge. You typically don't see "mixed" networks. It just makes things easier if either all the edges are lines, or all the edges are arrows.

An edge that starts and ends at the same vertex is called a loop. A network is called a simple network if it has:

  1. no loops, and
  2. no two vertices connected by more than one edge

Most networks we will see will be simple.

The first network is not simple because it has loops. The second network is not simple because there are “repeat” edges between some vertices. The third network is simple - no vertex is connected to itself, and no vertex is connected to any other in more than one way.

 

Walks and paths

A walk is the most general definition of how we can move around a network. If we start at a vertex and then move along an edge to a new vertex, we are starting a walk. If we have a directed network, we move in the direction of the arrows. 

We can continue the walk by selecting another edge coming out of the second vertex, then a third edge coming out of the third vertex, and so on. 

In a simple network we can represent a walk by a sequence of vertices. Here is a simple, undirected network, with the arrows representing a walk around the network:

We can record this walk as the sequence $\text{A, B, A, E, F, D, E}$A, B, A, E, F, D, E.

If a walk does not use the same vertex more than once (except for the start and end) we call it a path. Here are two different paths on the same network:

The path on the left is $\text{D, G, C, F, E, A}$D, G, C, F, E, A, and the path on the right is $\text{B, C, F, D, E, A, B}$B, C, F, D, E, A, B.

Here’s a quick summary of the definitions we’ve seen so far:

Summary

Vertex - A circle or dot in a network. Often given a vertex label.
Edge - A line segment connecting a vertex to a vertex. Can be directed (arrowhead) or undirected (no arrowhead). If it starts and ends at the same vertex, we call it a loop.
Network - A collection of vertices and edges. Can be directed (arrowheads) or undirected (no arrowheads). If there are no loops and no “repeat” edges, the network is simple.
Walk - A sequence of edges moving from one vertex to another in a network. If no vertex is repeated (except for the start and end), the walk is a path.
Path - A path is a walk where no vertex is repeated (except for the start and end).

Practice questions

Question 1

Which two of the following are valid networks?

  1. A

    B

    C

    D

Question 2

The following figure displays newspaper routes between several houses.

  1. The vertices are:

    The houses

    A

    The space enclosed by the routes

    B

    The routes

    C
  2. How many vertices are there?

  3. How many edges are there?

Question 3

Select the three simple networks:

(Remember that directed graphs can be simple!)

  1. A

    B

    C

    D

    E

    F

question 4

This question relates to the following network:

  1. Which three are valid walks?

    $K,F,P,K$K,F,P,K

    A

    $K,P,F,K,P$K,P,F,K,P

    B

    $K,P,F,R,M$K,P,F,R,M

    C

    $R,P,F,M,R$R,P,F,M,R

    D

    $K,P,F,K$K,P,F,K

    E

    $F,R,M,P,F$F,R,M,P,F

    F
  2. Which two of these are valid paths?

    $K,P,F,R,M$K,P,F,R,M

    A

    $K,P,F,K,P$K,P,F,K,P

    B

    $K,P,F,K$K,P,F,K

    C

What is Mathspace

About Mathspace