A very basic introduction to graph theory

Graph theory is a way of representing complex relationships for solving a particular algorithmic problem. It is a way of simplifying data that is only relevant to what you’re trying to solve.

In other words, it eliminates the perception of something that is deemed to be difficult to the reality that it can be easily computed.

So what is an example of graph theory?

Think about when you are planning a journey from A to B.

It doesn’t sound nearly as difficult when you say it, compared to when you picture it. It’s important to identify the steps you must take in order to get from your starting point to your destination. For example, you are planning a journey to get from the bottom to the top of the mountain but there are a few obstacles along the way… What do you do?

Create a path!

This is where graph theory comes in. You can use graph theory to reduce the complexities to get to the top of the mountain to complete your journey.

So there are different types of graphs. The picture above could be represented as an undirected graph because it clearly shows you a path to take from A to B and from B to A. It shows that you can go in any direction. In this example, you can go to the top of the mountain and back down again.

This is another example of using graph theory to simplify your journey. The reverse would be a directed graph where you can only go from A to B but you can not go from B to A.

A great example of using graph theory, would be on Google Maps. If you are trying to get from one place to another, it gives you clear directions you have to take. The reasons why it is not an undirected graph:

• It shows arrows that are pointing to a directed path.
• If you have completed your current journey and would like to go from your destination back to where you started, you would have to start a completely new journey. This shows that this particular example is a representation of a directed graph.

Did you notice something different on the graphs?

Before we get into this question, let’s look at the two graphs in a bit more detail. So the above graphs are typical representations of directed and undirected graphs. The circles that you see on the graph are called nodes or vertices and the straight lines and arrows that connect between the nodes are called edges. I have only demonstrated two ways of representing a graph, there are many others that I will get into a little later! Having fun?

So let’s go back to the question.

The thing that is different about these particular graphs is that some of the nodes have two or more edges connected to them. What does this mean?

It simply means that you are able to start from a particular node that has one or more edges and you get to choose which direction you would like to go. I hope that this is clear, if not, look at the graphs as you read this paragraph for extra clarity.

So, what is the significance of having one or more edges for a particular node? Isn’t that confusing? What is the actual purpose of it?

The answer to these questions involve more graphs to be explained. One of them is called a labelled graph which is shown above. A labelled graph is a graph that has some extra information attached to the edges between every two nodes.

A unlabelled graph is the opposite of this — it describes a graph that has no information attached to the edges, which is an example of the graphs we saw previously.

A labelled graph can be represented as a weighted graph. This graph also shows an example of a weighted graph that has a potential cost of traversing from one node to another that is connected by an edge…

Huh? Why does the extra information have a cost?

Well…

A cost can be determined in many ways. It might be that when you are planning a journey, it might cost you a lot of money or time to get from one node to another compared to when you take a different route that gives you a cheaper cost or a more efficient time-frame. For example, starting from node C in the graph above, what would be the cheapest or quickest edge to get to another node. Would it be node 5, 6 or 4?

It would be 4, of course. This shows that you are simplifying your journey to get from one node to another by using a weighted graph. A weighted graph has a similar algorithmic approach as Breadth-first search. If you’d like to know more about Breadth-first search and Depth-first search, please leave a comment below.

Hope you’ve learned a lot so far. There are some more graphs to know about…

Woah! What is going on here? Don’t be alarmed, this is as simple as the other graphs I’ve shown you… You can see that they’re both weighted, labelled, undirected graphs (because the edges have some cost on it, there are no arrows on the edges and there are some information attached to every edge). However, one of the graphs is a connected graph and the other is a bi-connected graph. Can you guess which one is which?

Yes, you are right! I’m guessing you are right…

So, the graph on the left is a connected graph because all the nodes that are traversing in the graph are connected by an edge. On the right, the graph shown is a bi-connected graph which describes a graph where some of its parts are connected and some are unconnected.

What is an unconnected graph? What does an unconnected graph look like? This describes a graph that is disconnected. In this example, Node 0 is not connected to any of the other nodes.

Last one! We are nearly finished…

Have you heard of a term in graph theory called isomorphic?

Well, for a graph to be isomorphic, it must be identical to another graph.

Take this example below. Both are not isomorphic — this means they are not the same.

Can you tell why?

The outside nodes and edges in the graph are similar. However, the two inner edges in the two graphs both are connected to different nodes but in different ways.

As you can see graphs can be represented in many different ways. Although, this is just a stepping stone of what graphs are all about. We have looked at most of the different types of graphs. Graphs have a huge contribution to our technology today, from maps to big data and so much more...

Before we wrap up, here is a little quiz. If you think you know the answer, try it out! Hint: consider the arrows and where they points to!

Which of these graphs are isomorphic?

Thank you so much, for reading, I hope you learned something new today.

Give a few claps, if you’d like more readings like this.

Next up, I will talk a bit more about graphs in depth and the common algorithms used in graph theory. These include: Euler Tours, Union-Find, Breadth-First Search, Depth-First Search, Dijkstra Algorithm, Kruskal’s Algorithm, Prim’s Algorithm. You can find out the answer to the exercise above in the next blog…

Bye for now…