The Basics of Graph Theory

Helene

·

Follow

Published in

Nerd For Tech

·

7 min read

·

Mar 17, 2021

151

Listen

Share

In this article, we will get a quick introduction to the basics of graph theory. We will talk about graphs in general — and the two classes they can fall into directed or undirected graphs. Afterward, we will also tackle another form of graphs — trees and so-called minimum spanning trees. This will all serve as the theoretical foundations for this series of articles where we will try to understand various algorithms which function upon graphs — for example, Depth and Breadth-First Search.

Graphs and Their Representation

Firstly, we need to understand what a graph is — and how we can recognize them when we see them in the wild. A graph is a structure amounting to a set of objects in which some pairs of the objects are in some sense “related”. The objects are called vertices, with one being called a vertex, and the relation connecting two vertices is called an edge. We can take a simple example to understand the idea behind it.

Let us imagine that we have two groups, A and B, of friends — each group has 3 members. Let us say group A consists of Edgar, Henry, and Jack. Group B consists of Max, Millie, and Bobby. We now want to model the friendship relations in these two groups of friends. Hence, the vertices are the different members — and the edges are whether there is a friendship between two individuals or not.

So, what does this graph tell us about the relations in and in-between our two groups of friends? Clearly, in the group, everyone is friends with each other — but we can also see there is a friendship between Jack and Millie, even though they are in different friendship groups. This is also called an undirected graph since the relation has no direction — Max does not only receive friendship from Bobby, but he also gives it back.

An adjacency matrix is a 2D array of size V x V where V is the number of vertices in a graph. Let the 2D array be adj[][], then adj[x][y] = 1 indicates that there is an edge from vertex x to vertex y. with undirected graphs, the adjacency matrix is always symmetrical

An adjacency list is an array of lists — The size of the array is equal to the number of vertices. For each vertex, there is a list of the vertices it is connected to. We can take an example to show the different possible representations: