Introduction to Graph Theory

Welcome to Teb’s Lab’s introduction to graph theory. What follows is an experimental educational project. It’s not quite a textbook, it’s not quite an online course, but rather it is an ordered collection of materials designed to help instructors and students alike learn the fundamentals of graph theory.

To me graph theory is the pinnacle of data structures and algorithms. It is a tragedy — albeit an understandable one — that so many “intro to data structures and algorithms” courses either gloss over or leave out graph theory. On the one hand, introducing students to arrays, linked lists, stacks, queues, hash tables, and trees is already quite an undertaking. Plus, graph theory is a sizable field unto itself.

On the other hand, bushwhacking our way through all these other data structures without unleashing the power of graphs is sort of like a crescendo without the climax. So, what is graph theory and why should you study it?

The Mathematics of Relationships

Graph theory is a subset of discrete math. It is used to model things that have relationships to other things — this vague definition hints at the enormous flexibility of graphs in problem solving. The remarkable power of graph theory has been used to solve problems in just about every discipline.

Municipal water system design uses graph theory to model water flow and ensure that pressure requirements are met. Social networks like Facebook and Twitter use graph theory to suggest friends and sell advertisements. Netflix uses graph theory to recommend movies. Google Maps uses graph theory to find the shortest path from your home to your destination. Internet infrastructure relies on graph theory to route your traffic from node to node on the physical infrastructure of the internet. Video game engineers use graph theory to route NPC’s through their virtual worlds.

Graph theory can also be used to model processes and decision making. State machines power a wide variety of algorithms from regular expressions to TCP’s congestion control mechanisms. Reinforcement learning algorithms (which power AlphaGo, OpenAI’s Open Five, and much more) are fundamentally built on top of graph theory.

In each of these examples there are things: people in a social network, intersections on the road, exchange points on the internet, decision points in a decision making process (such as a flowchart). Furthermore each of these things is connected to other things (sometimes of the same type, sometimes not) through some kind of relationship: people are friends in a social network; intersections are connected with roads; exchange points are physically connected to other internet nodes; taking actions from one decision point moves you to another decision point in a flow chart.

Graph theory is a unifying cornerstone of computer science. An understanding of graph theory gives programmers a guiding light in so many fields. Not only that, but it is such a useful mental model that once you start thinking in graphs you will notice them all around you.

For me personally, graph theory has been a transformational discipline that gives names and concrete details to a wide variety of natural and artificial phenomena. I hope it can do the same for you.

Project Goals: Open Source Education For Everyone

Teb’s Lab seeks to provide the highest quality learning materials and make it freely available to everyone, without limitation, in perpetuity. This project is an experiment in open source education and as such the written materials, code, diagrams, and supporting materials have been released to the public domain.

This material will introduce graph theory concepts and terminology as well as provide students with opportunities to practice important skills such as:

• Identifying examples of graph theory from a wide variety of disciplines.
• Describing different kinds of graphs.
• Reducing real world problems into graph theory problems.
• Identifying which kind of graph is most appropriate for a given problem.

While these theoretical underpinnings are powerful and important, this course is strongly rooted in the ideals of learning by doing. Furthermore, pragmatic applications of graph theory are plentiful and the implementation of graph based solutions to these problems is a powerful learning opportunity.

Included as part of this material is a Github repository which includes an implementation of a Graph API, tests for that API, and examples of using that API to solve problems in Python. We challenge you to implement your own graph API and use it to solve problems as well. Ours is provided as a scaffold to those ends, as well as a reference for readers.

Finally, we intend to extend and improve these materials over time. We are inspired by the software as a service model, and as our materials find their way into regular use we hope to cover much more than just the fundamentals of graph theory.

Lets dive into the first article, What Is a Graph? (or check out the table of contents)

If you wish to support our efforts to create and maintain these materials you can become a Patreon subscriber.