8.01 Introduction to graphs

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 network. Studying networks allows us to gain insights into any system of objects, people, places or ideas that have connections between them.

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.

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 - 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 graph describes a series of points and lines the represent connections. When studying networks, we often use the term graph to mean the same thing.

A point is called a vertex (or node). It is drawn as a dot or circle. The plural of vertex is vertices.

A line is called an edge (or arc or link)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 network (sometimes called a network graph, or just graph) is a collection of vertices with edges drawn between them.

Here are four different networks.

Let’s take a moment and notice a few things about the networks 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.

• One of the networks has numbered edges (weighted edges)

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 such as the name of a person, city, or animal or it can be more abstract, like a capital letter. In the networks 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 networks have labels that tell us what is being represented.

Examples

Example 1

Which two of the following are valid networks?

A

B

C

D

Worked Solution

Create a strategy

Check if the network has at least one vertex and all edges start at one vertex and end at one vertex

Apply the idea

For each option, each network has at least one vertex.

Options A and B are not valid networks because they have an edge that neither connects two different vertices nor connects the vertex to the edge.

Options C and D are valid networks since all edges start at one vertex and end at one vertex.

So options C and D are the correct answers.

Example 2

The following figure displays newspaper routes between several houses.

a

The vertices are:

A

The houses

B

The space enclosed by the routes.

C

The routes

Worked Solution

Apply the idea

The vertices are the houses since there are house names in each oval where the edges intersect.

So the correct answer is option A.

Watch question walkthrough

b

How many vertices are there?

Worked Solution

Create a strategy

Count the vertices in the network.

Apply the idea

There are 6 vertices.

Watch question walkthrough

c

How many edges are there?

Worked Solution

Create a strategy

Count the lines that connect vertices.

Apply the idea

There are 10 edges.

Watch question walkthrough

Edges can be either directed or undirected.

• Directed edges (also called arcs) are represented by arrows and symbolise a one-way relationship.

• Undirected edges are represented by lines and symbolise a two-way connection.

The first network has a directed edge because sharks eat fish and not the other way around - a one-way relationship.

The second network has an undirected edge because France and Spain share a border - a two-way relationship.

If there are directed edges in the network, we call it a directed network (or digraph). If there are no directed edges in a network, we call it an undirected network. Look back through the networks you’ve seen so far - those with arrows are directed, and the rest are undirected.

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:

We can still express a two-way connection using directed edges, we just have to draw in an extra (directed) edge. You typically don't see "mixed" networks - it just makes things easier if either all the edges are lines, or all the edges are arrows.

A network is connected when no vertices or group of vertices are isolated from the rest of the network. When a part of the network is isolated, it is said to be disconnected.

The top two networks are connected, the bottom two are disconnected.

An edge that starts and ends at the same vertex is called a loop. A network is called a simple network if it has:

1. no loops, and

2. no two vertices connected by more than one edge

Most networks we will see will be simple.

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.

Examples

Example 3

Which of the following are simple networks? Remember that directed graphs can be simple.

A

B

C

D

E

F

Worked Solution

Create a strategy

Choose the networks that has no loops and no two vertices connected by more than one edge.

Apply the idea

There is a loop in the network in option E.

There are two edges between a pair of vertices in the network in options B and F.

The network in options A, C, and D has no loops, and no "repeat" edges.

So the correct answers are options A, C and D.