An introduction to graph theory

Let’s think back to the previous activity. In that activity, you saw a problem that GigaFibre was experiencing whilst trying to grow their broadband network. When you were solving the puzzle about how to create the most efficient network of fibre optic cable, you didn’t need to know the geographical locations of the cities. It was sufficient that you knew the distances between the cities.

Graphs allow us to do exactly this; you can use them to model the relationships between objects. In the GigaFibre scenario, the relationships were between the eleven cities and each relationship had a distance associated with it.

You might be thinking that graphs are pictures that are used to plot functions such as the one below, and that’s true, but they can also help to describe the relationships between objects.

View the full size version of the image

Graph theory

Graph theory is a branch of mathematics that deals with the study of graphs, which are mathematical structures consisting of vertices (the singular of vertices is vertex) and edges. In graph theory, vertices represent objects or entities, and edges represent the relationships between them. Graphs are widely used to model various real-world systems, such as social networks, transportation networks, and computer networks, to name a few.

Graph theory provides a rich set of tools and techniques for analysing the properties and behaviour of graphs, including connectivity, shortest paths, flows, cycles, and many others. These tools have practical applications in various fields, including computer science, physics, biology, and many others.

Let’s break it down!

Vertices and edges

As we said, in graph theory the objects that the relationships are between are called vertices and the relationships are called edges. In the diagram below, vertices are represented as circles and edges are represented as lines between circles. (You have seen this already in the GigaFibre scenario in a previous activity:

Graph theory terminology

The following terminology will be useful later:

• A path is a sequence of vertices where an edge exists between at least two consecutive vertices:

• In a connected graph all the vertices are connected and there is no separate part, so between any two vertices there is a path between them. The graph on the left hand side below is a connected graph. The graph on the right hand side is a disconnected graph.

• A cycle is a closed path, that is, the first vertex in the sequence is also the last vertex in the sequence.

• A tree is a graph that is connected but has no cycles (ie. no closed paths):

Something to think about

Notice that the solution to the GigaFibre scenario was a tree. Why must a solution to any problem similar to the GigaFibre scenario be a tree? We will answer this later!

Next step

You should now have a solid understanding of how graphs can help to model the relationships between objects, using edges and vertices. Next, we’ll look at an efficient way to solve GigaFibre’s problem using something called Kruskal’s algorithm.