Graphs and networks
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.
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,\, B,\, C,\, D, and 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.
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.
Examples
Example 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?
Graph is a diagram consisting of a set of vertices connected by edges.
When graphs are applied to practical situations they are often referred to as networks. The terms graph and network are often used interchangeably.
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.
An edge represents a relationship between the objects or ideas that it links together, and the kind of relationship depends on the context.
Loop is an edge that starts and ends at the same vertex.
Multiple edges are two or more edges that start at the same vertex and finish at the same vertex.
Directed and weighted 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.
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.
Examples
Example 2
Consider the following network:
What is the weight of the edge from S to Q?
What is the weight of the entire network?
Networks can be represented by directed or undirected graphs and weighted graphs.
In a directed graph (or digraph) the edges indicate a one-way relationship and are represented by arrows.
An undirected edge is drawn as a line segment that begins and ends at a vertex.
A directed edge is drawn as an arrow that begins and ends at a vertex to represent a one-way relationship.
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.
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.
Bridges
If we can remove a single edge such that the graph is broken into two pieces, then we call that edge a bridge.
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.
Examples
Example 3
Which of the highlighted edges in the network is a bridge?
A bridge is an edge that would cause the graph to break into two pieces (become disconnected) if it was removed.
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.
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.
Examples
Example 4
Consider this network:
What is the degree of vertex C?
What is the degree of vertex D?
Isolated vertex is a vertex that has no edges connected to it, not even a loop.
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.