Graph Theory

Dr Ian Cornelius

Hello

Hello (1)

Learning Outcomes

Understand the concept of graphs and their purpose as a data structure
Demonstrate and implement their knowledge of graphs

Graph Theory

Graph Theory (1)

What are Graphs?

Graphs are the basis for a large amount of programming
They are essentially a set of nodes with connections between them
You may think of them as Lists: The Next Generation
- imagine a linked list, where any element of data can have as many next elements and as many parents as needed

The concept of graphs underpins a lot of the stuff that can be done in computer science and programming in general. Essentially, a graph is a series of nodes that have connections between them, and it may be helpful to think of these as if they are an advanced list, albeit the next generation.

For example, in a standard list we have an item which is followed by another, and then that item is followed by another item. However, with a graph, we can have multiple “next items” from a single item. This can be likened to the concept of moving from any given point in a graph to another place.

Let’s have a look at an example, on the screen you can see a diagram, and this is how a graph would be visually represented. We can see that we have our first node A, has a few connections to nodes B, C and D. Therefore, this item can have moved to anyone of these other nodes. For example, we could choose to go from node A to node D, to node C and then eventually to node E. Alternatively, another path we could take is to go from node A to node C to node E.

Graph Theory (2)

Use-cases for Graphs

Graphs can be useful for:
1. Map analysis, route finding, path planning
2. Ranking search results
3. Analysing related data such as social networks
4. Compiler optimisation
5. Constraint satisfaction
  - i.e. timetabling
6. Physics simulations
  - i.e. games
7. Social connections
8. Decision-making
  - i.e. goal-oriented action planning and strategies

There are a few different reasons as to why you may want to use graphs in your work. For example, you may want to use it for map analysis, such as finding a route between two given points. You may not be aware, but underlying the Google Maps software is a graph which can assist you in travelling from the campus buildings to your term-time address, or back home during the winter and summer break.

Alternatively, graphs can also be used for analysing related data, and this is commonly used in social media sites, such as Twitter (now known as ‘X’), Facebook and Instagram (collectively known as Meta). Graphs are also used in compiler optimisation to find potential paths of flow through the source-code.

Graph Theory (3)

Draws an edge between you and the people, places and things you interact with online
Whenever you like something on Facebook, it becomes an edge
- This edge is a connection between you and other people, places or things
Your photos, events and pages are connected with other information

I mentioned previously that graphs are utilised in social media. Let’s have a look at Facebook a little more in-depth.

You may not be aware, but your Facebook profile is a node in a large graph. Essentially, an edge (that is a connection) is drawn between you and the people, places and other things that you may interact with on the website, or online in general. What do I mean by this? Well, let’s look at this in a little more detail…

Think of yourself being at a party, standing in a circle with two of your friends (that means there are three of you). You reach out and touch your friends shoulder, and they then touch your shoulder and their friend, and their friend touches yours and that other friend. You are now all touching each other’s shoulders. These are the connections between you and the other people.

However, you begin to get hungry… but luckily for you, there is a pizza in the middle of the friendship circle. However, only two of you like pizza. Therefore, you and that other person become part of a network because you both expressed interest in pizza.

When you like something on Facebook, it becomes an edge between that object or property that you like and you. This edge is the connection between you and the other people, places and things. You can see on the screen a visual representation of how the Facebook social graph could potentially look like. From this graph, we can see that photos, events and pages are connected with other information such as your relationship to friends, and the type of stuff that you share, along with any photos that you may have tagged.

You may notice this happening in real life. For example, have you ever noticed the music you have listened to recently on Spotify is shared with your friends, and you can equally see the music they are listening to as well? Spotify was an early adopter of Facebook’s open graph platform to provide these connections.

Graph Theory (4)

Formal Terminology of Graphs

Graphs are a collection of nodes that have links between them
There are some terminologies you need to remember:
- nodes are called vertices
- links (connections between nodes) are called edges (or sometimes arcs)
  - an edge is an incident if it connects to another vertex
- connected vertices are called adjacent or neighbours
- a vertices degree is a number of edges that incident on it

By now you should understand that a graph is a series of nodes with connections that exist between them. Now it is time that we introduced the formal terminology associated with graphs. It ensures that when we discuss graphs with amongst ourselves, other people and developers, we are always using the same language, and they understand what you, or we are talking about.

Let’s begin with the term node, or nodes. This term refers to the data point in our graph. For example, on the screen a node is denoted as a circular object, i.e. those with the characters A, B and C etc. They may sometimes be referred to as a vertex for a singular node, or vertices when we are discussing multiple.

The connections between our nodes are referred to as edges, or sometimes as an arc. This will be the line connecting our nodes, for example, between node A and D we have a faint line, and this is our edge (or connection). It may sometimes be referred to as an incident when it connects to another vertex.

When a vertex is connected to another, they are referred to as being “adjacent” or neighbours. Finally, the degree of vertex is the number of neighbours or edges that connect to it. For example, node C has a degree value of three, as we have three nodes connected to it, A, D and E.

Types of Graphs

Types of Graphs (1)

There are many types of graphs:
1. Undirected
2. Directed
3. Vertex Labelled
4. Cyclic
5. Weighted
6. Connected
7. Disconnected
8. Directed Acyclic Graph (DAG)

Types of Graphs (2)

Undirected Graphs

Edges can be traversed in either direction
The vertices can be imagined as junctions on a road network
- the edges are a two-way road between junctions
- i.e. you can travel from node A to node B and then travel back from node B to node A

The first type of graph we shall be looking at is the undirected graph. With this type of graph, we can traverse between nodes in our graph in any given direction. For example, we could go from node A to node C and then to node D, going back to node C, and then to node B and then finally arriving back to node A. Alternatively, we may want to go from node A, to node B, to node C and then to node D. You could imagine these nodes as if they were connections in a map, and these connections between them are a two-way street, whereby you can travel in either direction.

Types of Graphs (3)

Directed Graphs

Each edge is directional and does not imply the inverse
The vertices can be imagined as junctions on a road network
- the edges are a one-way roads between junctions
- i.e. we can travel from node A to node C but we cannot travel back to node A

The next type of graph is directed graphs, and with these types of graph we are only able to travel in the direction indicated by the edge. For example, on the screen, you can see that our graph has an arrow pointing from node A to node C, meaning that we are only able to transition from node A to node C and we cannot move back from node C to A. Using our road analogy, this type of graph could be considered to be a one-way street, in which vehicles can travel along the road in only one direction. They are prohibited from driving down the stree in the opposite direction.

Types of Graphs (4)

Vertex Labelled

The data used to identify each node is not the only information that is important about that node
- i.e. it may also have a colour assigned to it that affects the algorithm decision or choice
The nodes can be imagined as roundabouts or slip-roads on a road network
- i.e. a red node is a heavily congested roundabout and should be bypassed

The next type is vertex labelled graphs, and these graphs are often used when additional information is required to be stored, rather than just being concerned with how the nodes are connected to each other. For example, you may want to include information regarding the type of colour a node is. These colours could indicate whether you want to traverse to that node or not. Using our road analogy, these colours could represent the congestion at a particular junction. For example, red is bad, and you would want to seek an alternative route, such as node D which has the colour green associated to it.

Types of Graphs (5)

Cyclic

Consists of at least one cycle
- i.e. there is a path that exists from a single node that can lead back to itself
Imagine our road network again; it is a roundabout where there is a vertex for each junction

The next type of graph is cyclic graphs, and as the name may suggest, they will have a form of cycle within them. On the right-hand-side of the screen, you can see an example of a graph, whereby moving from node B to D will result in a cycle. There is the option to continuously loop an infinite amount of time; however, there is also a break clause whereby you could transition to node F. A graph will be considered cyclic if there is at least one cycle, and is considered to be a path that goes from a node back to itself. Revisiting our road analogy, this is very similar to manoeuvring a round-a-bout, or a traffic island.

Types of Graphs (6)

Weighted

Parameters along edges or at nodes are interval data and can be summed and/or compared
This is similar to vertex labelled but more versatile
Thinking about the road network example, the weight of our graph edges could be according to the speed limit
- it could mean the algorithm would favour faster roads over a slower road in route planning

Another variation of a graph is the weighted graph, whereby each of the edges between a node will have a weight associated with them. These are sometimes known as ‘costs’, the cost of moving from one node to another. When it comes to thinking about our roads, this would represent the distance that we are required to travel before we reach the end of a road.

Applying this to the diagram on the screen, the distance between nodes A and B have a cost of two, which in our road analogy could stand for two miles. This could be useful information for deciding on how we would go about traversing a graph or our route back home, and this will make a lot more sense in a later lecture.

Types of Graphs (7)

Connected

There is an edge between every pair of nodes in a graph

Types of Graphs (8)

Disconnected

There is a node that does not have any connection to a node in the graph
- the red node makes our graph disconnected

Types of Graphs (9)

Directed Acyclic Graph (DAG)

Links in these graphs have a direction and there are no cycles
It consists of vertices and edges, where each edge is directed from one vertex to another
- they follow the directions of the other nodes and never form a closed loop
It Can be visualised like a river system heading out to sea
- it may fork and join at parts, but it always does so going downstream

Degrees, In-degrees and Out-degrees

Degrees, In-degrees and Out-degrees (1)

Recap: Degrees count the number of edges connected to a node
Three types of degrees for a graph:
1. degree
2. in-degree
3. out-degree

We shall now have a look at the concept of degrees and how they are applicable to a graph and its nodes. To recap, a degree is the number of edges that are connected to a specific node. The degree of a graph can be represented in three ways: degree, which is the total number of connections (in and out), in-degree, which is the total number of connections going into the node, and out-degree, which is the total number of connections leaving the node.

Over the next couple of slides, we shall look at a few examples of graphs, and how we would go about counting the number of degrees these graphs contain.

Degrees, In-degrees and Out-degrees (2)

Undirected Graphs

Concerned with only counting the total number of connections for a node
- in this instance, the degree

Vertex	Degree
A
B
C
D
E
F

When it comes to an undirected graph, we are only concerned with counting the total number of connections for each node. Therefore, in this instance we only count the degree for each node and this can be represented in the form of a table.

On the right-hand-side of the screen you can see our graph, and to the left, you will see a table representing each vertex that we have in our graph. We are then tasked to go through each vertex and provide a number for the total number of connections that are made to that node.

Click Populate

For example, node A has a total of two connections, and we can see from our graph that we have a connection from node A to nodes B and E. Therefore, in our table we shall populate our degree number to be two for vertex A.

Click Populate

Let’s have a look at another example, and look at node D. For this node, we can see that we have connections to nodes C, E and F, therefore, a total of three degrees. Therefore, we populate in our table for node D the value three.

Click Populate

Degrees, In-degrees and Out-degrees (3)

Directed Graphs

Concerned with counting:
- the total number of connections, known as the degree
- the number of incoming connections, known as the in-degree
- the number of outgoing connections, known as the out-degree

Vertex	Degree	In-Degree	Out-Degree
A
B
C
D

When it comes to a directed graph, we are concerned with counting the total number of connections, as well as the incoming and outgoing connections. Therefore, in this instance, we are going to be counting the degree, in-degree and out-degree for each node. This can be represented in the form of a table, as you can see on the screen.

Click Populate

For example, node A has a total of two connections, with both of them going out to nodes B and C. Therefore, we populate our degree value to two, our in-degree as zero (as we do not have any incoming connections), and our out-degree as two.

Click Populate

Let’s have a look at a second example, and examine node C. For this node, we can see that there are a total of four connections. Therefore, we populate our degree value as four. Out of these four connections, it can be observed that there are two incoming connections, one from node A and the other from node D, and therefore we can populate our in-degree as two. Finally, we look at our out-degree, and we can see that from node C there are two outgoing connections, one to node B and the other to node D. We, therefore, populate our table with the out-degree value as two.

Click Populate

Representation of Graphs

Representation of Graphs (1)

Mathematical Notation

The elements of a graph can be represented in different methods:
- vertices with integers (or any unique value)
- edges as a pair of vertices, i.e. (1, 0)
A graph G will consist of a set of vertices V and a set of edges E
- represented as G = (V, E)
n and m can be used to represent the number of vertices and edges
- think n for node if you find it difficult to remember which way around these go
G = (V, E), where,
- V = [A, B, C, D, E]
- E = [(A,B), (B,D), (C,D), (C,E), (D,E)]
Final form:
- \(G = ([A, B, C, D, E], [(A,B), (B,D), (C,D), (C,E), (D,E)])\)

We shall now move on and look at the formal representation of a graph in our code using mathematical notation. Well, firstly, we can represent each of the vertices in our graph as integers, in fact, anything can do, but quite often in programming we like to use a numbers. The edges of these nodes would be represented as a pair of vertices, in this case (1, 0) pair on our screen is a connection between vertices 1 and 0.

A graph which is represented as an uppercase G will have a set of vertices and a set of edges. Therefore, we can represent this as G = (V, E), where V and E represent the vertices and edges, respectively. There may be cases, where sometimes use n and m to represent the number of vertices and edges. You can think of this as n for node if you find it difficult on which way around they would go.

Let’s have a look at an example of how we would represent this in the notation we have just described. The graph on the right-hand-side of the screen will be represented as G, which contains a list of vertices, V, and edges, E.

Our list of vertices in this instance is our nodes, so they would be A, B, C, D and E. Whereas our edges, would be the list of connections between our nodes. For example, they would be (A,B), (B,D) and (C, E) etc. This would then come together as our final mathematical notation, shown on the screen.

Representation of Graphs (2)

Programming Methodology

When it comes to representing a graph in programming, there are two ways of implementing a graph:
1. Adjacency Matrices
2. Adjacency Lists

Representation of Graphs (3)

Adjacency Matrices

A two-dimensional matrix of boolean values
- the value of a cell (i, j) is true if the vertices are connected
Adjacency matrices are symmetrical along the diagonal for undirected graphs
However, for directed graphs a connection (1, 2) does not imply a connection between (2, 1)
Adjacency matrix requires \(O(n^2)\) space, where \(n\) is the number of vertices
Code Representation:

aGraph = [
  [False, True, False, False, False],
  [True, False, False, True, False],
  [False, False, False, True, True], 
  [False, True, True, False, True],
  [False, False, True, True, False]
]

Tabular Representation:

	A	B	C	D	E
A		T
B	T			T
C				T	T
D		T	T		T
E			T	T

Here is an example of how you can represent a graph as an adjacency matrix in Python programming code, and as a tabular form. On the right-hand-side of the screen, you can see the graph that is being represented in the source-code and table on the left. For this undirected graph, we have a link between nodes A and B and therefore, the same connection will exist between nodes B and A. Therefore, you can see in row one and column two, and row two and column one of our tables; we have placed the True boolean value.

This can also be reflected in our Python source-code. You will see in our code that a list has been created called, aGraph, which contains a collection of lists in a list, known as a multidimensional list. The first list in our list is the first row of our table. For each value of T in our table, we provide the value True in our list, and False for any empty entry that exists in the table.

Therefore, looking at our multidimensional list, we can see that the first list that exists in it has only a single True value at index one . The first list in our multidimensional list is for all connections on node A, therefore, the True value at index one would represent the connection to node B.

Let’s have a look at our second list in the multidimensional list, , this list represents all the connections for node B and we can see from this list that we have a True value at indices zero and three. These represent our connections from node B to nodes A and D, respectively.

However, this would not be the case for a directed graph, as a connection between nodes A and B does not imply that there is a connection between B and A.

Representation of Graphs (4)

Adjacency List

Each vertex contains a list of vertices that it is connected to the other
- often stored as a dictionary in Python
Adjacency lists requires up to \(O(n+m)\) space
- where \(n\) is the number of nodes in our graph and \(m\) is the number of edges
Code Representation:

aGraph = {
  "A": ['B'],
  "B": ['A', 'D'],
  "C": ['D', 'E'],
  "D": ['B', 'C', 'E'],
  "E": ['C', 'D']
}

Tabular Representation:

Vertex	Adjacency List
A	B
B	A, D
C	E, D
D	B, C, E
E	C, D

When it comes to representing a graph as an adjacency list, they are often stored as a dictionary in Python. Each node in the graph will be a key in our dictionary, which would then store a value that contains a list of nodes connected to that node.

On the screen, you will see the graph on the right-hand-side that we want to represent as both a dictionary in Python and as a table. In the table representation, you will see that for each vertex in our graph, we have a corresponding list of nodes that are connected to it. For example, vertex D consists of connections to nodes B, C and E, respectively.

As we have just discussed, when it comes to our Python code, the table can be represented as a dictionary. Whereby, a key in the dictionary will be a vertex that exists in the graph. The value that will be stored by that key will be a list of nodes that connect to that given vertex. For example, the key C in our dictionary contains a list with the values D and E. As we can see from our graph, for this vertex, there are connections to D and E.

Representation of Graphs (5)

Recap: Weighted Graphs

It is sometimes useful to store a number with each edge
- this will change the way the graphs are represented
The adjacency matrix is now numerical instead of boolean
Unconnected nodes can be given a default value, such as infinity (\(∞\)) for shortest path finding
The adjacency list must sture edges as pairs, including the connection and the weight
- For example, a tuple could easily be represented using a simple struct with two variables
  - int neighbour and float weighting
  - i.e. (0, 5.0)

We have spoken previously about weighted graphs. In these cases, we have to think differently about the way in which we record them. When it comes to using an adjacency matrix, the values are now numerical instead of boolean. Any nodes that may be unconnected can be given a default value such as infinity, which would be useful for the shortest path finding algorithms, which you will be introduced to in a later lecture. We cannot use zero as that looks like an edge which does not have cost associated with it completely.

Adjacency lists on the other-hand will store edges in pairs, including the connection and weight. For example, a tuple could easily represent this sort of data.

Representation of Graphs (6)

Adjacency Matrix — Weighted

For a weighted adjacency matrix, boolean values are replaced with numbers
- i.e. the cost of traversing from one node to another
Note: That if your weightings are positive floating point values
- may benefit you by making the False values a negative number, i.e. -1, rather than checking for == 0.0f
Code Representation:

aGraph = [
  [-1, 5, -1, -1, -1],
  [5, -1, -1, 7, -1],
  [-1, -1, -1, 4, 8], 
  [-1, 7, 4, -1, 3],
  [-1, -1, 8, 3, -1]
]

Tabular Representation:

	A	B	C	D	E
A		5
B	5			7
C				4	8
D		7	4		3
E			8	3

When it comes to representing weights in an adjacency matrix, as we have discussed before, we change our boolean value to the cost that is associated with moving along that edge. On the right-hand-side of the screen, you can see our graph that contains a collection of weights for each edge that exists between the nodes. On the left, you will see the code and tabular representation of the graph.

Instead of using the True and False boolean values, we now use numbers to represent the weight of connections between the nodes. In languages that have some value that does mean not a number, we can use that value in place of the numbers. If you do not, you can use a very large value or a low negative value. This must be some sort of default which you know will not be the weight of an edge and must be used consistently throughout. In cases like this, I prefer to use minus one to represent an edge without a weight.

Representation of Graphs (7)

Adjacency List — Weighted

For a weighted adjacency lists, connected nodes have an associated weight provided next to them
- i.e. a number provided in brackets
Code Representation:

aGraph = {
  "A": [('B',5)],
  "B": [('A',5), ('D',7)],
  "C": [('D',4), ('E',8)],
  "D": [('B',7), ('C',4), ('E',3)],
  "E": [('C',8), ('D',3)]
}

Tabular Representation:

Node	Adjacency List
A	B(5)
B	A(5), D(7)
C	E(4), D(8)
D	B(7), C(4), E(3)
E	C(8), D(3)

The last example for this lecture we shall look at is representing our weighted graph as an adjacency list. As I have discussed previously, we can store our list in Python as a dictionary item, whereby each key:value pair in our dictionary, would be a vertex and a list of nodes that connect to it. However, this time we need to modify our list of nodes to include the weight that is associated with that connection.

To do this, we can use a tuple, which would contain two items. The first is the connecting node, and the second the weight of the connection. On the screen, you will see I have updated our adjacency list dictionary object from earlier. This time, I have modified our list of connected nodes to be a tuple pair, and I include the weight of the connection. For example, from node A to node B there is a cost of 5, therefore, we add the value of that cost to our tuple. Alternatively, for our table representation, we provided the weight inside a set of round brackets next to the node.

Goodbye

Goodbye (1)

Questions and Support

Questions? Post them on the Community Page on Aula
Additional Support? Visit the Module Support Page
Contact Details:
- Dr Ian Cornelius, ab6459@coventry.ac.uk

Graph Theory

Dr Ian Cornelius

Hello

Hello (1)

Learning Outcomes

Graph Theory

Graph Theory (1)

What are Graphs?

Graph Theory (2)

Use-cases for Graphs

Graph Theory (3)

Facebook: The Social Graph

Graph Theory (4)

Formal Terminology of Graphs

Types of Graphs

Types of Graphs (1)

Types of Graphs (2)

Undirected Graphs

Types of Graphs (3)

Directed Graphs

Types of Graphs (4)

Vertex Labelled

Types of Graphs (5)

Cyclic

Types of Graphs (6)

Weighted

Types of Graphs (7)

Connected

Types of Graphs (8)

Disconnected

Types of Graphs (9)

Directed Acyclic Graph (DAG)

Degrees, In-degrees and Out-degrees

Degrees, In-degrees and Out-degrees (1)

Degrees, In-degrees and Out-degrees (2)

Undirected Graphs

Degrees, In-degrees and Out-degrees (3)

Directed Graphs

Representation of Graphs

Representation of Graphs (1)

Mathematical Notation

Representation of Graphs (2)

Programming Methodology

Representation of Graphs (3)

Adjacency Matrices

Representation of Graphs (4)

Adjacency List

Representation of Graphs (5)

Recap: Weighted Graphs

Representation of Graphs (6)

Adjacency Matrix — Weighted

Representation of Graphs (7)

Adjacency List — Weighted

Goodbye

Goodbye (1)

Questions and Support