Graphs and networks
What do roads, human ancestry, currency exchange, planning a wedding, and the internet have in common? They are all things that we can represent with a mathematical object called a network. Studying networks will allow us to gain deep insights into any system, place, or thing that is defined by its connections.
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 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.
A network (sometimes called a network graph, or just graph) is a collection of vertices with edges drawn between them.
Here are three more networks - these have letters or words for each vertex.
Vertices in networks are often given vertex labels. These labels can be something specific (the name of a person, city, or animal...) or it can be more abstract, like a capital letter.
Examples
Example 1
The following figure displays newspaper routes between several houses.
The vertices are:
How many vertices are there?
How many edges are there?
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 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.
Types of edges
Directed edges are represented by arrows and symbolise a one-way relationship, while undirected edges are represented by lines and symbolise a two-way connection.
If there are directed edges in the network, we call it a directed network (or digraph). If there are no directed edges, we call it an undirected network.
Q: What about if there's a mix - some arrowheads, some lines?
A: 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:
An edge that starts and ends at the same vertex is called a loop.
A simple network has
no loops, and
no two vertices connected by more than one edge
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.
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 (arrowhead) or undirected (no arrowhead). If there are no loops and no “repeat” edges, the network is simple. A network is also referred to as a graph.
Create networks
Let's investigate how the capitals of each Australian state and territory are connected by the road network. Here’s a map:
Now let’s draw the major roads connecting these cities together as undirected edges (since you can go back and forth along the roads), and get rid of the state names:
I have added in three extra vertices (Katherine, Threeways, and Port Augusta) along the road from Adelaide to Darwin where it branches off to other cities. Without them we would have a single edge (road) connecting more than two vertices, which is not allowed.
Now we can get rid of the underlying map, and are left with the connections between the capital cities as a network:
If we only care about if we can get from one city to another, and not how far it is between the cities, we can simplify the network a lot:
Now we can easily see all kinds of information:
You can’t drive straight from Canberra to Perth without going through at least one other capital city along the way.
If you’re in Hobart you can drive around but you’re never going to any other capital city (this is a loop)
If you want to go from Melbourne to Sydney you can go through Canberra or you can drive around it.
It’s not to scale anymore, but that’s ok - here we are only interested in whether cities are connected.
You will see networks are actually all around you once you know how to look for it. For example, here is the London tube map as a network:
By sacrificing realism and only representing the information we care about (which stations are connected to which other stations and how), using the map becomes easier.
Examples
Example 2
Within a water system the feeding chain can be described as follows:
Tadpoles, Water Beetles and Snails all survive by eating algae.
Small Fish eat the tadpoles, whilst frogs survive on water beetles and snails.
The kingfisher, a skillful fishing bird, survives on eating small fish and frogs.
Which of the following graphs represents the feeding chain? Note that the arrows point from the thing that is eaten to the thing that eats it.
Example 3
A beach volleyball social competition team can have 3 players on the court at any time. The team has 5 players at the tournament. The table shows 3 combinations that the coach has already used in the first three games.
| Games | Players chosen |
|---|---|
| 1 | Ryan, Jimmy, Lucy |
| 2 | Lucy, Beth, Ellie |
| 3 | Ellie, Ryan, Jimmy |
Which of the following graphs shows the combinations of players that have already played together?
There is one more game left in the tournament. Who should the coach choose to play so that every team member has played with every other team member at least once?
Some situations that can be represented by graphs or networks. Vertices can represent objects or places, edges can represent paths or connections, and weights can represent numerical data that connects the vertices like times or distances.