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.
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.
When studying networks a graph describes a series of points and lines the represent connections.
A point is called a vertex (or node). It is drawn as a dot or circle. The plural of vertex is vertices.
A line is called an edge (or arc or link) and it 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.
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.
Connected network
A network is connected when no vertices or group of vertices are isolated from the rest of the network. When a part of the network is isolated, it is said to be disconnected.
The top two networks are connected, the bottom two are disconnected.
Simple network
An edge that starts and ends at the same vertex is called a loop. A network is called a simple network if it has:
- no loops, and
- 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.
Here’s a quick summary of the definitions we’ve seen so far:
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).
Loop - An edge that starts and ends at the same vertex.
Network - A collection of vertices and edges. Can be directed (arrowheads) or undirected (no arrowheads).
Simple - A network is simple if there are no loops and no “repeat” edges.
Connected - A network is connected when no vertices or group of vertices are isolated from the rest of the network.
Practice questions
Question 1
Which two of the following are valid networks?
A
B
C
D
Question 2
The following figure displays newspaper routes between several houses.
The vertices are:
The houses
AThe space enclosed by the routes
BThe routes
CHow many vertices are there?
How many edges are there?
Question 3
Select the three simple networks:
(Remember that directed graphs can be simple!)
A
B
C
D
E
F