Graph Theory De-mystified

Hello everyone! In this post, I want to cover elementary graph theory. Don’t worry, as intimidating as graph theory sounds, the concepts should be intuitive. In order to make this material as simple as possible, I’m going to omit all formal proofs from the discussion of graphs. I will also not delve into the formal definitions of certain ideas, such as the distinction between a simple graph and a multi-graph. On the other hand, the discussions done here will help you remember concepts, not theorems! With that said, let’s dive right into graphs!

Introduction to Graphs

I’m sure most of you have heard the word “graphs” being thrown around in a plethora of different contexts. But what exactly denotes a graph? Before we get into the cool stuff, there is some terminology that I will assume you know.

A graph is basically a set of nodes or vertices connected by edges. As you can see, the universality of graphs is apparent from its definition. Any set that is connected through edges can essentially be transformed into a graph. The classic example of a graph is the social network, Facebook. On Facebook, you, the user, are a vertex in a complex network where edges represent friendship. When you add a friend on Facebook, you are creating an edge between you and your friend in the Facebook graph.

Screen Shot 2015-05-03 at 3.03.19 PM

The degree of any vertex is the number of edges that the vertex is connected to. Sticking to the Facebook analogy, the degree of any person is the number of friends he/she has.

Applications

Let’s say you are at a fancy cocktail party and when you arrive, everyone shakes everyone else’s hand. You want to find how many handshakes have occurred if there are 10 people at the party.

Every person should have shaken hands with 9 people. Thus, you would expect 10*9 handshakes = 90 handshakes. However, our approach would count the handshakes between a pair of people twice. Thus, logically, we must divide our answer by 2 to get 45 total handshakes.

An easier way to approach this problem is using a graph. People will be vertices in the graph, and edges between two people will represent that those two people have shaken hands. We want to find the number of edges in the graph. We know that there are 10 vertices and every person will shake hands with 9 people. The Handshaking Theorem captures the observation we made above, and claims that the sum of the degrees of all the vertices will be twice the number of edges in the graph. The sum of the degrees of all the vertices in our graph is just 9, or the number of people each person shakes hands with. We must divide the number of vertices (10) * degree of each vertex (9) by 2 because each edge logically contributes two to the sum of the degrees of all the vertices. Thus, the answer is the same: 45 total handshakes.

The Handshaking Theorem is one small application of the use of graphs, but there is much more that can be captured with the power of graphs.

Bipartite Graphs

Bipartite graphs come up in several applications (discussed at the end of this section). To get an intuitive sense of bipartite graphs, let’s reuse the Facebook analogy. The definition of a bipartite graph is a graph that can be partitioned into two disjoint sets such that every edge connects a vertex in one set to a vertex in the other set. What!? If you’re like me, that definition wasn’t at all useful at first glance.

What is a bipartite graph really? If you had a bipartite Facebook graph, you could assign every person one of two groups where that person was not friends with anyone else in that group and all of his/her friends were in the other group. As an example, let’s take a Facebook graph consisting of Bob, John, Rohit, Megan, Norman, and Margaret. The friendships are as described as follows (an arrow denotes friendship):

Graph

For this graph to be bipartite, you need to be able to divide the graph into two groups where nobody is friends with each other. See if you can come up with a way to divide these group of people.

Note: For a graph to be bipartite, you have to be able to classify everybody in the graph in either group without violating the rule of creating groups where no one is friends with one another. If you can’t do this, the graph is NOT bipartite.

The following is a representation of the same graph that shows that this graph is bipartite:

BipartiteGraph

You could easily come up with this representation by starting with a vertex (Bob) and putting that person in one group and putting all of his/her connections in the second group (John, Margaret). Then, repeat that process for a person in the second group (John for example) , and so on. If the graph is bipartite, you will be able to complete this process without leaving anyone behind.

As an extension for those that are interested, you will most probably come across various theorems related to the bipartite property of any given graph. For example, any discussion of being bipartite is incomplete without a discussion of graph coloring. 

Graph coloring is very similar to finding groups of people on Facebook that are not friends with each other. Let’s say you were to find 4 groups of people on Facebook where nobody was friends with anyone else in their group. Then, this graph would be 4-colorable in technical terms. Graph coloring is just a way of assigning a color to each of these groups. A fancy way of saying this concept is that you must assign a color to each vertex of a graph so no two adjacent vertices are assigned the same color.

Bipartite graphs are a special case of using 2 colors to divide a graph. Thus, a bipartite graph is 2-colorable intuitively.

Applications:

You may be thinking as to why bipartite graphs would be useful besides finding two groups of people in a social network where nobody is friends with one another. Bipartite graphs occur surprisingly often in the real world because of the occurrence of pairs everywhere. For example, using a bipartite graph, you could solve the problem of finding an ideal marriage arrangement so that everyone is happy (Hall’s Marriage Theorem). There is a variety of literature on problems that use Hall’s Marriage Theorem, all of which are interesting. The way to model a marriage problem is to have a certain number of men paired with women (for the sake of the problem, let’s assume heterosexual marriages). The men would be in one group, and the women would be in another group. A bipartite graph will capture the relationships between the men and women.

Interestingly enough, the game Settlers of Catan involves a graph coloring problem. You cannot place settlements on adjacent vertices of the hexagon on which one settlement is located. If you want to program a computer to play Settlers of Catan, there is probably a graph representation you must deal with!

There are also some awesome things you can derive about a graph given it is bipartite. For example, if a graph is bipartite, the sum of the degrees of every vertex in one group is equal to the sum of the degrees of every vertex in the other group. Using the marriage analogy, this translates into the simple idea that an edge between a man and a woman contributes to the degree of both the vertices of the man and the woman.

Also, every subgraph of a bipartite graph has to also be bipartite. (Here are the proofs for them)

Euler Circuits

Another cool application of graphs is to Euler circuits.

Let’s say you are traveling to a friend’s house in another city. You take a combination of roads to get to your friend’s house, stay there for a while, and then take the same roads back or maybe a faster route.

This situation can be easily represented using a graph. Consider the geographical map represented as a graph. Roads will be edges and cities will be the vertices. A path is a route in the graph from one vertex to another (your house to your friend’s house). A circuit is a special type of path that starts and ends in the same vertex (starting at your house and ending up back at your house). For the scope of this post, we will only consider circuits with non-repeated edges. This means a circuit starting at your house must take a completely different path going to and returning from your friend’s house.

I want to specifically talk about Euler circuits. Euler circuits are circuits that use every edge in the graph. Going back to the previous analogy, if you were in a city with only 10 roads, an Euler circuit would start at your house, go to your friend’s house, and come back to your own house while traveling through all 10 roads ONLY once.

Obviously, that sounds impractical while just going to your friend’s house, but Euler circuits are very useful in other settings. One interesting application of an Euler circuit could be to a postal service car route that wants to travel through all the roads in a city without retracing its steps.

Now, you’re probably wondering whether every graph has an Euler circuit, or how easy it is to find an Euler circuit? Let’s work through an analogy to come up with a mechanism to find out whether a graph has an Euler circuit. In a city with 10 roads, your goal as a postman is to travel through all 10 roads without repeating any roads and starting and ending at the same location: the post office. If you start at the post office and take Road A, it is already assumed that you cannot take Road A again to get back to the post office because that would violate our rules. So, we have established that there has to be at least more than one road from the post office in order for an Euler circuit to exist. In fact, any vertex in your graph has to have more than one road connected to the vertex, otherwise you will be stuck at that vertex in your route. Logically, we can then deduce that every vertex must have a road to travel INTO the vertex and to travel OUT of the vertex. Mathematically, this translates into the fact that every vertex must have even degree (a route in and route out of the vertex) in order for an Euler circuit to exist. There is a theorem that captures this intuitive explanation: Any connected multigraph with at least two vertices contains an Euler circuit if and only if every vertex has even degree.

I won’t go into the algorithm for finding an Euler circuit because it is basically just an application of the observation we made above, but the algorithm is called Fleury’s algorithm.

Hamiltonian Circuits

Now that you have an idea for what an Euler circuit, we can get into Hamiltonian circuits, which are very similar to Euler circuits. In an Euler circuit, we wanted to travel through all the edges in the graph exactly once. In a Hamiltonian circuit, we want to travel through all the vertices in the graph exactly once (excluding the first and last vertex obviously). This can be confusing because of its extreme similarity to Euler circuits, so let’s take an example.

Let’s say you were a tourist touring certain monuments in the U.S. Starting from your hotel, you want to visit a certain number of monuments without passing by any of the monuments twice, and then return to your hotel. When you sit down to find this optimal route, you are essentially looking for a Hamiltonian circuit. This is different from an Euler circuit because you don’t care about repeating certain roads; instead, you only care about visiting all the monuments in an efficient order.

Algorithms to find a Hamiltonian circuit in a graph are much harder. In fact, the traveling salesman problem is just the problem of finding a Hamiltonian circuit. You might have heard that this problem is NP-complete, which means there is no efficient algorithm developed yet that can solve this problem.

Why is all of this useful?

Hopefully, you can already get a feeling that graph theory is very useful in the world. This post only covers a sliver of the literature out there on graph theory. Circuits are very useful in the real world, in social networks, maps, flow networks, etc. Graphs are everywhere in all fields, whether it be in biology, business, computer science, or architecture. If you are interested in the inner workings of graphs because you need to satiate your thirst for math, either take a discrete mathematics class 😉 or check out: Graph Theory Explained. I hope you found this post easy to follow and interesting!

Advertisements

One comment

  1. Raden Gerald Agustin · January 28, 2016

    Nice work!

    Like

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s