11.01 Introduction to networks (Extension)

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.

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.

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.

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:

Practice questions

Question 1

Question 2

Question 3

question 4