A Gentle Introduction To Graph Theory
Tags: graphtheory, computerscience, math
Published: 2017-03-21 14:55:39

---
title: A Gentle Introduction To Graph Theory
published: true
description: Graphs are all around us, we just donâ€™t always see them for what they are.
cover_image: 
tags: graph-theory,computer science, math
---

So many things in the world would have never come into existence if there hadnâ€™t been a problem that needed solving. This truth applies to everything, but _boy, is it obvious_ in the world of computer science.

Someone needed a way of keeping track of the order of things, so they played around with and created [different data structures](https://dev.to/vaidehijoshi/whats-a-linked-list-anyway) until they found the one that worked the best for the specific problem that they were trying to solve. Someone else needed a good way of storing data, so they played around with [different number systems](https://dev.to/vaidehijoshi/hexes-and-other-magical-numbers) until they found one that worked best for the kind of information that they wanted to contain. People needed a good way of labeling and processing tasks, so they found a way to [build upon the tools](https://dev.to/vaidehijoshi/to-queue-or-not-to-queue) they had and created a way to juggle all the things that one single system needed to do, at any given time.

Of course, computer science isnâ€™t the _only_ field to innovate and build upon what came before it, but I do think that itâ€™s unique in one way: _computer scienceâ€™s innovations rely and build upon its own abstractions._

Iâ€™ve talked about abstractions a whole lot in this series, because ultimately, thatâ€™s what this series is _about_: finding the joy in the abstractions that lie beneath the things that all of us use, every single day. And, for what itâ€™s worth, when I say â€œusâ€, Iâ€™m only partially talking about _us_ as programmers, the producers of technologyâ€Šâ€”â€ŠI also mean _us_ as users, the consumers of technology.

So, which amazing abstraction shall we learn about next? Well, now that weâ€™re experts in tree data structures, it only seems right to understand where trees came from. Trees are actually a subset of something you might have already heard about: **graphs**. But in order to truly know why we use graphs and what they are, weâ€™ll need to go deep down to the very roots of something that stems from discrete mathematics: **graph theory**.

If this is your very first foray into discrete math, fear notâ€Šâ€”â€Šitâ€™s mine, too! Letâ€™s tackle it togetherâ€Šâ€”â€Šand try not to lose our sanity in the process.

### Looseyâ€“goosey graphs

When we first started looking at non-linear structures, we learned about their most fundamental characteristic: that their data doesnâ€™t follow an orderâ€Šâ€”â€Šat least, not an obvious numerical one, like we see in arrays or linked lists. Trees, [as we learned](https://medium.com/basecs/how-to-not-be-stumped-by-trees-5f36208f68a7#.hzdufmviz), start with a root node, and might connect to other nodes, which means that could contain subtrees within them. Trees are defined by a certain set of rules: one root node may or may not connect to others, but ultimately, it all stems from one specific place. Some trees have even _more_ specific rules, like [binary search trees](https://medium.com/basecs/leaf-it-up-to-binary-trees-11001aaf746d#.x8kftrftl), which can only ever have _two_ links to _two_ nodes at any given time.

But what if we did something kind of crazy and justâ€¦threw these rules out the window? Well, as it turns out, we totally _can_ do that! Itâ€™s just that we wouldnâ€™t be dealing with trees anymoreâ€Šâ€”â€Šweâ€™d be dealing with something called a **graph**.

> Trees are nothing more than restricted types of graphs, just with many more rules to follow . A tree will always be a graph, but not all graphs will be trees.

So, what is it that makes a tree different from the large umbrella of graphs?

Well, for one thing, a tree can only flow in one direction, from the root node to either leaf nodes or child nodes. A tree can also only have one-way connectionsâ€Šâ€”â€Ša child node can only have one parent, and a tree canâ€™t have any loops, or cyclical links.

![](https://cdn-images-1.medium.com/max/800/1*rguQ2Y2Z920IYGkO0cHHtQ.jpeg)

With graphs, all of these restrictions go straight out the window. Graphs donâ€™t have any concept of a â€œrootâ€ node. And why would they? Nodes can be connected in any way possible, really. One node might be connected to five others! Graphs also donâ€™t have any notion of â€œone-directionalâ€ flowâ€Šâ€”â€Šinstead, they might have direction, or they might have no direction whatsoever. Or, to complicate matters further, they could have some links that have direction and others that donâ€™t! But we wonâ€™t get into that today.

Letâ€™s stick with the simple stuff to start.

### Graphs with direction, and graphs without

Okay, so we know that graphs pretty much break all the rules that we know. However, there is one characteristic that every graph _must_ have: every graph always needs to have, at the very least, one single node. Just as how trees need at least one root node in order to be considered a â€œtreeâ€, similarly, a graph needs at least a single node in order to be considered a â€œgraphâ€. A graph with just one node is usually referred to as a **singleton graph**, although we wonâ€™t really be dealing with those.

Most of the graphs weâ€™ll be dealing with are a bit more complex. But, donâ€™t be worriedâ€Šâ€”â€Šwe wonâ€™t be diving into the _super complicated_ graphs today. And trust me, some graphs really are complicated!

Instead, letâ€™s look at the two types of graphs that are pretty easy to spot, and also pretty common in graph theory problems: directed graphs, and undirected graphs.

As we know, there are no real rules in the way that one node is connected to another node in a graph. Edges (sometimes referred to as _links_) can connect nodes in _any_ way possible.

![](https://cdn-images-1.medium.com/max/800/1*sdUlnmnwMcPQljH52HiYBQ.jpeg)

The different types of edges are pretty important when it comes to recognizing and defining graphs. In fact, thatâ€™s one of the biggest and most obvious differentiators between one graph and another: the types of edges that it has. For the most part (aside from one exception, which we wonâ€™t cover today), graphs can have two types of edges: a edge that has a direction or flow, and an edge that has no direction or flow. We refer to these as _directed_ and _undirected_ edges, respectfully.

In a **directed edge**, two nodes are connected in a very specific way. In the example below, node A connects to node B; there is only _one_ way to travel between these two nodesâ€Šâ€”â€Šonly one _direction_ that we can go. Itâ€™s pretty common to refer to the node that weâ€™re starting from as the _origin_, and the node that weâ€™re traveling toas the _destination_. In a directed edge, we can **only travel** **from the origin to the destination**, and never the other way around.

![](https://cdn-images-1.medium.com/max/800/1*nXh55HVMJavGwzSB5jS_-Q.jpeg)

However, itâ€™s an entirely different story with undirected edges. In an **undirected edge**, the path that we can travel goes both ways. That is to say, the path between the two nodes is _bidirectional_, meaning that **the origin and destination nodes are not fixed**.

This differentiation is actually pretty important, because the edges in a graph determine what the graph is called. If all of the edges in a graph are _directed_, the graph is said to be a **directed graph**, also called **digraph**_._ If all of the edges in a graph are _undirected_, the graph is said to beâ€Šâ€”â€Šyou guessed itâ€Šâ€”â€Šan **undirected graph**! Go figure, right?

![](https://cdn-images-1.medium.com/max/800/1*cS26jONjjQ5ACImJmHhtqg.jpeg)

This is all very cool, but at this point, I want to know two thingsâ€Šâ€”â€Šwhere did all of this graph stuff _come from_, exactly? Andâ€¦why should we care?

Letâ€™s investigate.

### Tread lightly: weâ€™re in graph country now

Computer science loves to borrow stuff. More specifically, it has borrowed a lot of concepts from logic and mathematics. As it turns out, this is the case with graphs.

Graph data structures as we know them to be computer science actually come from math, and the study of graphs, which is referred to as **graph theory**.

> In mathematics, graphs are a way to formally represent a network, which is basically just a collection of objects that are all interconnected.

As it turns out, when computer scientists applied graph theory to code (and ultimately implemented graphs as data structures), they didnâ€™t change a whole lot. So, a lot of the terms that we use to describe and implement graphs are the exact terms that weâ€™ll find in mathematical references to graph theory.

For example, in mathematical terms, we describe graphs as **ordered pairs**. Remember high school algebra, when we learned about _(x,y)_ ordered pair coordinates? Similar deal here, with one difference: instead of _x_ and _y_, the parts of a graph instead are: **_v_**, for _vertices_, and **_e_**, for its _edges_.

The formal, mathematical definition for a graph is just this: **G = (V, E)**. Thatâ€™s it! Really. I promise.

![](https://cdn-images-1.medium.com/max/800/1*zAmHaDww1A31Esup-Rmr-w.jpeg)

But hang on a secondâ€Šâ€”â€Šwhat if our graph has more than one node and more than one edge! In factâ€¦it will pretty much _always_ have multiple edges if it has more than one node. How on earth does this definition work?

Well, it works because that ordered pairâ€Šâ€”â€Š_(V, E)_â€Šâ€”â€Šis actually made up of **two** **objects**: a _set_ of vertices, and a _set_ of edges.

Okay, that makes more sense to me now. But it would be a whole lot clearer if I had an example and actually wrote out the definition of a graph! So weâ€™ll do just that. In the example below, we have an undirected graph, with 8 vertices, and 11 edges.

![](https://cdn-images-1.medium.com/max/800/1*goT8sipQbDIoogV6Kc_3KA.jpeg)

So whatâ€™s going on here?

Well, we wrote out our ordered pair _(V, E)_, but because each of _those_ items is an object, we had to write those out as well. We defined _V_ as an _unordered_ set of references to our 8 vertices. The â€œunorderedâ€ part is really important here, because remember, unlike trees, there is **no hierarchy of nodes**! Which means that we donâ€™t need to order them, since order doesnâ€™t matter here.

We also had to define _E_ as an object, which contains a bunch of edge objects within it. Notice yet again that our edge objects are also _unordered_. Why might that be? Well, what type of graph is this? Is there any direction or flow? Is there a fixed sense of â€œoriginâ€ and â€œdestinationâ€?

Nope, thereâ€™s not! This is an _undirected_ graph, which means that the edges are bidirectional and the origin node and destination node are _not_ fixed. So, each of our edge objects are also **unordered pairs**.

This particularity, of course, leads us to wonder: what if this were a **directed** graph? Time for another example! Hereâ€™s a directed graph, with three vertices and three edges:

![](https://cdn-images-1.medium.com/max/800/1*ThD5bfLUyEx49s5S9qKKow.jpeg)

The way we define the vertices here doesnâ€™t look any different, but letâ€™s look more closely at our edge definition. Our edge objects in this case are _ordered_ pairs, because direction actually matters in this case! Since we can only travel from the origin node to the destination node, our edges _must_ be ordered, such that the origin node is the first of the two nodes in each of our edge definitions.

Cool, so thatâ€™s how we define graphs. Butâ€¦when would we ever actually _use_ graphs? Well, you probably used one today. You might just not know it yet! Time to change that.

### Super social graphs

Graphs are all around us, we just donâ€™t always see them for what they are.

In fact, by the very act of reading this post, you are _literally on a graph right now._ The web is a massive graph structure! When we click between websites and navigate back and forth between URLs, weâ€™re really just navigating through a graph. Sometimes those graphs have nodes with edges that are undirectedâ€Šâ€”â€ŠI can go back and forth from one webpage to anotherâ€Šâ€”â€Šand others that are directedâ€Šâ€”â€ŠI can only go from webpage A to webpage B, and never the other way around.

But thereâ€™s an even better example that beautifully illustrates our daily interactions with graphs: social networks.

Facebook, a massive social network, is a type of graph. And if we think more about it actually functions, we start to better understand _how_ we can define, and exactly what _type_ of graph it is. On Facebook, if I add you as a friend, you must accept my request. Itâ€™s not possible for me to be your friend on the network without you also being mine. The relationship between two users (read: nodes or vertices in graph terms!) is _bidirectional_. Thereâ€™s no concept of an â€œoriginâ€ and a â€œdestinationâ€ nodeâ€Šâ€”â€Šinstead, youâ€™re my friend and I am yours.

Can you guess what type of graph Facebook is implemented as?

![](https://cdn-images-1.medium.com/max/800/1*qxvZX-YRBsRrmM5ePvNAQA.jpeg)

If you guessed _undirected graph_, then youâ€™re right! Well done. Relationships are two-way, so if we were to define Facebookâ€™s friend network as a graph, its edges would all end up being unordered pairs when we wrote them out.

Twitter, on the other hand, works very differently from Facebook. I can follow you, but you might not follow me back. Case in point: I follow Beyonce, but she definitely does not follow me back (sadly).

![](https://cdn-images-1.medium.com/max/800/1*urJTrfWn8aZdhb9A-HXZVg.jpeg)

We could represent Twitter as a _directed_ graph. Each edge we create represents a _one-way_ relationship. When you [follow me on Twitter](https://twitter.com/vaidehijoshi), you create an edge in the graph with your account as the origin node, and my account as the destination node.

So what happens when I follow you back? Do I change the edge you created when you followed me? Does it suddenly become bidirectional? Well, no, because I could unfollow you at any given point. When I follow you _back_ on Twitter, I create a second edge, with _my_ account as the origin node and yours as the destination.

The same model applies to dev.to, as well, which lets you follow and unfollow authors! In fact, this network model is _all over the place_. And all it is, once we abstract all the layers away, is a graph. And truly, what a powerful thing it is.

### Resources

Lots and lots of entire _books_ have been written about graphs. I certainly didnâ€™t cover enough information here to fill a book, but that doesnâ€™t mean you canâ€™t keep learning about graphs! Fill your mind with more graph theory awesomeness, starting with the great links below.

1.  [Difference between trees and graphs](http://freefeast.info/difference-between/difference-between-trees-and-graphs-trees-vs-graphs/), Poonam Dhanvani
2.  [Whatâ€™s the difference between the data structure tree and graph?](http://stackoverflow.com/questions/7423401/whats-the-difference-between-the-data-structure-tree-and-graph), StackOverflow
3.  [Applications of Graph Theory In Computer Science: An Overview](http://www.cs.xu.edu/csci390/12s/IJEST10-02-09-124.pdf), S.G.Shirinivas et. al.
4.  [Graph Traversal](http://www.cs.jhu.edu/~cohen/CS226/Lectures/GraphTraversal.pdf), Professor Jonathan Cohen
5.  [Data Structures: Introduction To Graphs](https://www.youtube.com/watch?v=gXgEDyodOJU&t=319s), mycodeschool