The Hitchhiker’s Guide to Graphs
Work in Progress
Preface
What do the World Wide Web, your brain, the corpus of scientific knowledge accumulated by all of humanity, the entire list of people you’ve ever met, and the city you live in have in common?
These are all very different types of things, from physical, to virtual, to social in nature, but they share a very important trait. They are all networks that establish relationships between some entities.
The World Wide Web is a network of interconnected computational resources, data, software, and hardware infrastructure. Your brain is a network of interconnected neurons. The accumulated human knowledge is also a network of interconnected ideas, as all discoveries depend upon prior knowledge, and unlock new discoveries. The city you live in is also an interconnected network of roads and buildings. And the people you know is also network, as many of them know each other, or know someone that knows someone you know.
As distinct as these things are, they all share common properties, by virtue of their networked nature. For example, you can think of how “close” two entities in this network are. The meaning of “distance” will be different if you’re considering physical networks (like roads) versus information networks (like published papers with citations to other papers) versus social networks (like your Facebook friends), but in all cases there is some sense in which some entities are “closer” together than others.
What if we could study this abstract notion of networks, and understand their fundamental properties all at once?
Welcome to graph theory.
Welcome to Graph Theory!
To study these seemingly disparate objects in the deepest possible way, we need an abstract concept that captures the fundamental notion of things connected together. In mathematics and computer science, they are called graphs. Graphs lie at the intersection of mathematics and computer science, and their study is one of the most fascinating branches of math, science, and human knowledge in general.
This book is a journey through the theory and applications of graphs, synthesizing the practical and the mathematical points of view. In each chapter, we will look at one specific problem and see how it can be translated into the language of graphs. Then we will design a computational strategy – an algorithm – to solve that problem, or at least to attempt an approximation – because some problems are too hard to solve them completely. In doing so, we will also look at the underlying theory that makes our solution work.
In the next few hundred pages, we will teach you almost everything we know about graphs, including their most intriguing mathematical properties, but also their most practical uses to solve real-world scientific, engineering, and social problems.
Thus, when you’ve finished reading this book, you will have a solid understanding and familiarity of graphs, similar to the level expected from a Computer Science graduate in most curricula out there. (And perhaps deeper in some niche topics that are usually not taught in a CS major.)
What this book is (and what is not)
This book is not a textbook for a computer science course. There are plenty of wonderful books you can use if you’re learning (or teaching) about graphs at college. The most essential of these books is Introduction to Algorithms1, which I strongly recommend you check out if you want a more traditional – and complete – introduction to, well, algorithms in general and graphs in particular. It is the best selling book in the history of computer science.
This book will cover both some of the simplest and some of the most advanced algorithms and concepts in graph theory, so there is no single one-semester course where all this content could be taught. Depending on your background and interests, this book will serve you in different ways.
If you are a Computer Science student, think of this book as a complement to all you will see in college. As you learn about graphs in different subjects, you can come to this book and find algorithms, theorems, and proofs suitable to the level of depth you’re exploring.
If you are a CS professor, this book can give you some cool ideas to introduce specific graph theorems and algorithms, along with clean and simple reference implementations. The explanations are also more intuitive than what you can find in more traditional textbooks. The book also features follow-up questions and problems that you can mix-and-match with your own to enrich your classes or exams.
If you are a software developer, you can use this book to complement your knowledge about graphs, or fill any gaps you may have from your background studies. You can also use it as a quick reference to many of the most used graph algorithms, and as an inspiration to introduce graph theory into your current projects, perhaps improving some of your work.
If you are a casual coder, this book will give you plenty of cool problems to play with and ideas to build some cool projects on your own. It may even give you the inspiration to go deeper into other computer science fields such as AI and optimization.
And if you are none of the above, you can still enjoy this book. Some of the most beautiful ideas in math emerge naturally from graph theory. In any case, as I’ll try to convince you in this book, graphs are everywhere. Knowing more about them can only help you see the world around you with a new pair of glasses, and that’s always a good thing.
Prerequisites
This book assumes some basic knowledge of programming. If you have some experience with the Python programming language, you’ll find it easier to understand the code examples. However, even if you’ve never seen Python before, a minimal familiarity with any programming language will probably be more than enough, since Python is super intuitive – at least its small subset that we’ll use throughout this book. If you’re new to Python or need a refresher, check the Appendix B — A Primer on Python for a quick intro to the basic features of the language that we’ll need in this book.
If you have never, ever seen a programming language before, then the coding part of this book will be harder for you. However, you can still enjoy the intuitive and visual explanations and the mathematical proofs, and skip all the code. We will always present an informal explanation of any algorithms that we study. And if getting the most out of this book is the nudge you need to learn a little bit of coding, even better!
Regarding math, you should be at least comfortable with high-school level, but no college-level math is necessary. Specially, no advanced calculus or algebra appears anywhere in this book. The majority of the proofs use only basic logic, and we’ll introduce any mathematical tool we need – such as strong induction or reductio ad absurdum – in the Appendix A — A Primer on Logic. That being said, some minimal previous exposure to discrete math won’t hurt you.
How to read this book
This book is divided into several parts that are more or less independent. Except for 1 Introduction, all other chapters can be read roughly in any order, although the first few chapters introduce the most important algorithms. In some cases a later chapter may reference a previous result or algorithm, but in those cases you’ll find an explicit link to any required content.
Thus, unless you’ve already familiar with the basic notations and concepts in graph theory, I recommend you read the 1 Introduction first. Afterwards, you’re free to hop around and take any chapter that suits your interest.
Actually, we can model the problem of reading this book as a graph problem, where each chapter is a node, and the edges indicate dependencies. In this graph, you can quickly find what is the optimal way to read the book if you are only interested in some chapters, so that you are guarantee to cover all pre-requisites. We will solve this very problem in ?sec-toposort.
Each part deals with solving problems of a similar nature, and is divided into chapters that grow in complexity. That means, say, the last chapter of Part 2 may be more advanced than the first chapter of Part 4.
Each chapter is dedicated to solving one specific problem, introducing ideas and algorithms that emerge from our journey towards the solution. In each chapter, we will
- understand and mathematically formulate the problem,
- build intuitions to channel our ideas towards the solution,
- and discover the solution in the form of a theorem or an algorithm. If it’s an algorithm, we’ll build a reference implementation in Python as well.
Intermixed between all of this, we’ll drop some theoretical sections that delve into the underlying math and provide some formal proofs. These sections will be clearly marked and are absolutely optional, so you are free to skip them, at least on a first read.
And to keep things a bit on the fun side, instead of simply tackling dry, boring, abstract graph problems, we will frame our discussions in the context of the fictional city of “Graphtopia”, where all citizens are crazy about graphs and everything is done using graph theory.
In summary, you can read this book top-to-bottom, or you can skim and jump around as much as you want.
Complementary source code
This book comes with by a simple Python library called hitchhikers-graphs that contains all the code we’ll write and use throughout the book. You will find a short reference for this library in the Appendix C — The hitchhiker-graphs Python Package.
The library itself is open-source and can serve as a starting point for other projects, but it is not designed to be a production-ready solution for solving graph problems. It is merely an educational device, designed to help you truly understand graph theory. For this reason, all implementations are purposefully oversimplified and more care is given to clarity and simplicity than performance.
That being said, you’re free to download, modify, and use it as you see fit.
A word on notation
This book follows the standard mathematical notation for graphs that you can find anywhere, and we will learn that notation in due time, incorporating new concepts as we need them.
Most of the math- and code-heavy parts are optional and clearly marked so you can decide whether to skip them or dive into them. This is how you identify them:
- \(\small(\Sigma)\) All sections or blocks marked with this symbol are math-heavy, and usually include proofs for theorems just discussed in the previous sections.
- \(\small[\lambda]\) All sections or block marked with this symbol are code-heavy, and most often include a Python implementation of an algorithm previously discussed.
For emphasis: although you can definitely skip these sections and still enjoy and get a lot out of this book, we strongly encourage you to, at least on a second read, give them a try. We’ve made our best to be as clear and intuitive as possible even in these more advanced sections.