4.01 Introduction to 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.

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,\, 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.

This graph has a loop at vertex A and multiple edges between vertices D and F.

Examples

Example 1

Consider the following graph.

a

Which vertex is isolated?

Worked Solution

Create a strategy

Choose the vertex that is not connected to the other vertices.

Apply the idea

Vertex B is not connected to any other vertices by any edges.

So vertex B is isolated.

b

How many edges are there in the network?

Worked Solution

Create a strategy

Count the edges (lines) in the network.

Apply the idea

There are 7 edges.

c

How many vertices are there?

Worked Solution

Create a strategy

Count the vertices (circles) in the network.

Apply the idea

There are 5 vertices.

d

Which vertex is the loop connected to?

Worked Solution

Create a strategy

Choose the vertex that has an edge that starts and ends at itself.

Apply the idea

The loop is connected to vertex A.

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.

We have seen that the edges of a graph can be given numerical values like the graph on the left.

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.

Examples

Example 2

Consider the following network:

a

What is the weight of the edge from S to Q?

Worked Solution

Create a strategy

Use the weight of the edge from vertex S that points to vertex Q.

Apply the idea

The number 7 is written beside the edge that from S pointing to Q.

So the weight is 7.

b

What is the weight of the entire network?

Worked Solution

Create a strategy

Add all the weights in the network.

Apply the idea

\displaystyle \text{Network weight}	\displaystyle =	\displaystyle 14+10+13+9+6+4+7	Add the weights
	\displaystyle =	\displaystyle 63	Evaluate

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.

Examples

Example 3

Which of the highlighted edges in the network is a bridge?

A

Edge 3

B

Edge 2

C

Edge 1

D

Edge 4

E

None

Worked Solution

Create a strategy

Choose an edge that would cause the graph to break into two pieces.

Apply the idea

If edge 1 is removed it will disconnect the network. One part will have vertices A, B, C, E, F, and the other part will just have vertex D.

The correct answer is option C.

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:

a

What is the degree of vertex C?

Worked Solution

Create a strategy

Count the number of edges going into or out of vertex C.

Apply the idea

Vertex C is only connected by one edge.

The degree of vertex C is 1.

b

What is the degree of vertex D?

Worked Solution

Create a strategy

Count the number of edges going into or out of vertex D.

Apply the idea

Vertex D is connected to three edges.

The degree of vertex D is 3.