Introduction to Graph Theory

My favorite subject in Theoretical Computer Science: Graph Theory. Maybe you think this is a graph:

And if you do, then you’d be right, but if you are a student of Mathematics or Computer Science, the term graph probably means something like this:

And for this site, we distinguish these two definitions by calling the first depiction a plot of a function and the second a graph defined by vertices and edges. Note, we also call the graph a network, where the vertices are called nodes and the edges are called connections or links. In this post we will talk about the importance of graph theory and share a few examples, and in a later post we will go into the technical formalisms.

Graphs in the World

Graphs can represent connections and traversals, so they are present in all kinds of Relational Data such as social networks or the internet, Traversal Data such as maps, logistics or airline routes, or Flow Data such as inventory flow. We will now explore a few of these examples to bring out some intrigue in the subject.

First let’s consider the social network. The following is an example of a fairly small one.

In this example, the vertices represent people in the social network and the edges represent two friends like on Facebook. In this way, by analyzing the graph itself we can draw conclusions for the social network. For example, finding small worlds in social networks can be done by looking for clusters of vertices tightly connected to each other in our social network graph. This is one example that emphasizes the importance of Graph Theory, and, in fact, studying social networks is an active field of research in Theoretical Computer Science.

Another example is navigation where understanding how to get from one place to another is important. This can be represented by graphs as well, and I’ll present the age-old problem that birthed the subject of Graph Theory by the famous Leonhard Euler in the 18th century.

Take a look at the Seven Bridges of Königsberg below. The bridges are colored in as brown.

The goal was to find a path that crosses over every bridge without crossing a bridge twice. Try for yourself, and I can guarantee you won’t find such a path. Euler recognized that since we only cared about the bridges, we can abstract this city map to the following graph.

Now it is equivalent to simply looking for a path that traverses every edge, and through the development of Graph Theory we can conclude that this is impossible, and, hence, there is no path that crosses all seven bridges without double-crossing.

This is another example where Graph Theory can solve such traversal problems. This certain example is very small-scaled, but even navigation algorithms for our daily use or optimizing airline routes all employ Graph Theory.

Another interesting example is in the case of inventory management which falls under Flow Data. Consider a company called Toilet Paper Factories, and they have their factory in Riverside, and they have a network of trucking channels between cities with capacities on the number of crates that can go through that channel daily. We depict this setting in the following graph where the edge labels represent the daily capacities. Our goal is to transport the inventory from the factory to their warehouse in San Jose.

Now we wish to determine the daily maximum number of crates we can transport from the factory to the warehouse with these given parameters on capacity. And in fact, we can use Max-Flow Algorithms to solve this, and this is also another example of the use of Graph Theory in the world.

Having given a brief overview of some applications of Graph Theory, I hope you are interested in learning Graph Theory formally, and upcoming posts will reflect this theory mindset.