 4.01 Introduction to graphs and networks

Lesson

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.

Warning!

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.

Summary
 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. 1. Which vertex is isolated?

2. How many edges are there in the network?

3. How many vertices are there?

4. Which vertex is the loop connected to?

Question 2

Consider the following network: 1. What is the weight of the edge from $S$S to $Q$Q?

2. What is the weight of the entire network?

Question 3

Consider this network: 1. What is the degree of vertex $C$C?

2. What is the degree of vertex $D$D?

Types of graphs

We have already discussed some terms that describe different properties of graphs and we have considered directed, undirected and weighted graphs. This graph is undirected and weighted. This is a directed weighted graph.

Here we will see some other ways to classify graphs.

Connected graph

A graph is connected when no vertices or group of vertices are isolated from the rest of the graph. When a part of the graph is isolated, it is said to be disconnected The top two graphs are connected, the bottom two are disconnected.

If we remove a bridge from a connected graph the graph will become disconnected.

Complete graph

We call a graph on $n$n vertices complete if every vertex is connected to every other vertex. There is exactly one complete graph for each value of $n$n. The degree of each individual vertex is equal to one less than the number of vertices overall. In other words, if you take $n$n vertices and connect one to all the others, you draw $n-1$n1 edges from each vertex.

Simple graph

A graph is called a simple graph if it has:

1. no loops, and
2. no multiple edges. The first graph is not simple because it has loops. The second graph is not simple because there are multiple edges between some vertices. The third graph is simple - no vertex is connected to itself, and no vertex is connected to any other in more than one way.

Subgraph

A graph is called a subgraph (or subnetwork) when all vertices and edges are also the vertices and edges of another graph.

If we take a graph and delete some edges, or some of its vertices (and all edges connected to it), we obtain a subgraph of the original.

For example, any simple graph that has $n$n vertices is a subgraph of the complete graph with $n$n vertices - we can just add or delete edges to get from one to the other: The graph on the left has the red edges added in, and then the vertices moved a little.

We end up with a complete graph.

Bipartite graph

A bipartite graph is a graph whose vertices can be divided into $2$2 groups such that each edge connects a vertex from one group to a vertex in another.  Vertices in a group are never connected to other vertices in that group. You can see the two groups of vertices (top and bottom) and how each edge joins a node from the top group to the bottom group.

A bipartite graph does not have to be drawn in with the groups of vertices arranged in rows (although they usually are).

The graph below is bipartite - the green vertices form one group and the purple vertices form another and all the edges join a green and purple vertex. Types of graphs
 directed graph (digraph) Edges indicate a one-way relationship and are represented by arrows weighted graph Edges are assigned a number that can represent some property, such as distance or cost. Weighted graphs may be directed or undirected. connected graph No vertices or group of vertices are isolated from the rest of the graph. When a part of the graph is isolated, it is said to be disconnected. complete graph Every vertex is connected by an edge to every other vertex simple graph An undirected graph that contains no loops or multiple edges. A simple graph can be connected or disconnected. subgraph All vertices and edges are also the vertices and edges of another graph. bipartite graph Vertices can be split into two groups, where each edge connects a vertex from one group to a vertex in the other group.

Practice questions

Question 4

Consider the following network: 1. What two changes could be made to make this network simple?

Remove the loop at $B$B.

A

Remove an edge between $E$E and $B$B.

B

Remove an edge between $C$C and $A$A.

C

Remove the loop at $F$F.

D

Remove the loop at $B$B.

A

Remove an edge between $E$E and $B$B.

B

Remove an edge between $C$C and $A$A.

C

Remove the loop at $F$F.

D

Question 5

Consider the following two graphs:  Graph 1 Graph 2
1. Is Graph 2 a subgraph of Graph 1?

Yes

A

No

B

Yes

A

No

B

Question 6

In a connected graph:

1. There is an isolated vertex.

A

There are no loops.

B

Each vertex is linked to another vertex only through one edge.

C

Every vertex is reachable via some path from every other vertex.

D

There is an isolated vertex.

A

There are no loops.

B

Each vertex is linked to another vertex only through one edge.

C

Every vertex is reachable via some path from every other vertex.

D

Question 7

Which of the highlighted edges in the network is a bridge? 1. Edge 3

A

Edge 2

B

Edge 1

C

Edge 4

D

None

E

Edge 3

A

Edge 2

B

Edge 1

C

Edge 4

D

None

E

QUESTION 8

Which of the following graphs are complete bipartite graphs?

Select all that apply.

1. A B C D A B C D

Outcomes

ACMGM078

explain the meanings of the terms: graph, edge, vertex, loop, degree of a vertex, subgraph, simple graph, complete graph, bipartite graph, directed graph (digraph), arc, weighted graph, and network