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 graph.
The roads and towns in this map form a graph.
The components and wiring in this electronic circuit are represented as a graph.
In mathematics, the term graph refers to a diagram that consists of a set of points, called vertices, that are connected by a set of lines called edges. When we are using graphs for practical applications, we often use the term network to mean the same thing.
Studying graphs allows us to gain insights into any system of objects, people, places or ideas that have connections between them.
You have seen graphs 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 graphs 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 - graphs and 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 graph 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. 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 graph is a collection of vertices with edges drawn between them.
Let’s take a moment and notice a few things about the graphs 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.
- The edges in the last graph have a numerical value.
- In the first graph it's not possible to travel from a red vertex to a blue vertex via any edges.
- In the other three graphs it's possible to travel from one vertex to any other vertex via edges.
Here are three more graphs - these have letters or words for each vertex:
Vertices in graphs are often given labels. The 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 graphs 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 graphs have labels that tell us what is being represented.
Directed graphs
Edges can represent a one-way connection or a two-way connection.
- Directed edges (also called arcs) are drawn as arrows and represent a one-way connection.
- Undirected edges are represented by lines and represent a two-way connection.
The first graph has a directed edge because sharks eat fish and not the other way around - a one-way relationship.
The second graph has an undirected edge because France and Spain share a border - a two-way relationship.
If there are directed edges in the graph, we call it a directed graph (or digraph). If there are no directed edges, we call it an undirected graph.
A graph that is shown with edges that are a mix of arrows and lines is still a directed graph, where the lines represent a two-way connection. "Mixed" graphs like this are not common. It makes things easier if either all of the edges are lines, or all of the edges are arrows. We can redraw such a graph by replacing two-way edges with a pair of directed edges. An example is shown below:
Weighted graphs
We have seen that the edges of a graph can be given numerical values like the graph below:
These values are called weights and can represent some property such as distance or cost. When the edges of a graph have weights we refer to the graph as a weighted graph. The weight of the graph is the sum of the weights of all edges.
Loops and multiple edges
An edge that starts and ends at the same vertex is called a loop.
When there are two or more edges that start at the same vertex and finish at the same vertex, we refer to these as multiple edges.
This graph has a loop at vertex $A$A and multiple edges between vertices $D$D and $F$F.
Bridges
If we can remove a single edge such that the graph is broken into two pieces, then we call that edge a bridge.
The three orange edges are bridges.
Deleting any bridge will break the graph into two parts, with no connection between the parts. If any other edge is deleted, the graph will remain in a single piece.
Degree of a vertex
The degree of a vertex is the number of edges that either go into or out of a vertex, where loops are counted twice. This number tells us how many ways we can move from that vertex to another (or even the same) vertex within the graph.
A useful trick is to make a ring close around the vertex. Count the number of times that edges cross the ring at a vertex, and we will have the degree.
Each vertex has a small ring placed around it and the number of crossings is counted.
If you do it this way you’ll always remember to count loops twice.
A vertex is referred to as odd if the degree of the vertex is odd; and referred to as even if the degree of the vertex is even.
If the degree of a vertex is zero, then there are no edges connected to it (not even a loop), and it is called an isolated vertex.
| graph |
A diagram consisting of a set of vertices connected by edges. In a directed graph (or digraph) the edges indicate a one-way relationship and are represented by arrows. In a weighted graph, edges are assigned a number that can represent some property, such as distance or cost. Weighted graphs may be directed or undirected. |
| network |
When graphs are applied to practical situations they are often referred to as networks. Examples include transport networks, a food web, and the results of a sporting competition. Networks can be represented by directed or undirected graphs and weighted graphs. The terms graph and network are often used interchangeably. |
| vertex (or node) |
The fundamental building block of a graph and represents a single object or idea. It is drawn as a dot or circle. |
| edge |
An edge represents a relationship between the objects or ideas that it links together, and the kind of relationship depends on the context. An undirected edge is drawn as a line segment that begins and ends at a vertex. A directed edge (also called an arc) is drawn as an arrow that begins and ends at a vertex to represent a one-way relationship. |
| loop |
An edge that starts and ends at the same vertex. |
| multiple edge |
Two or more edges that start at the same vertex and finish at the same vertex. |
| bridge |
An edge that would cause the graph to break into two pieces (become disconnected) if it was removed. |
| isolated vertex |
A vertex that has no edges connected to it, not even a loop. |
| degree |
The degree of a vertex is the number of edges that connect to the vertex. Loops are counted twice. For an odd vertex the degree is an odd number. For an even vertex the degree is an even number. For an isolated vertex the degree is zero. |
| weight |
the weight of an edge is a numerical value that represents a property such as distance. The weight of a graph is the sum of the weights of all the edges. |
Practice questions
Question 1
Consider the following graph.
Which vertex is isolated?
How many edges are there in the network?
How many vertices are there?
Which vertex is the loop connected to?
Question 2
Consider the following network:
What is the weight of the edge from $S$S to $Q$Q?
What is the weight of the entire network?
Question 3
Consider this network:
What is the degree of vertex $C$C?
What is the degree of vertex $D$D?
Question 4
Which of the highlighted edges in the network is a bridge?
Edge 3
AEdge 2
BEdge 1
CEdge 4
DNone
E