The Hitchhiker's Guide to Graphs (early access)

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, but they share an essential trait. They are all networks that establish relationships between some entities.To study these disparate objects in the deepest possible way, we need some abstract concept that captures the fundamental notion of things connected together. In mathematics and computer science, this concept is called a graph.This book is a journey through the theory and applications of graphs. In each chapter, we will look at one specific problem and see how it can be translated into graph problems. 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 completely. In doing so, we will also look at the underlying mathematical theory that ensures our solution works.In a few hundred pages, I will teach you almost everything I know about graphs, including their most intriguing mathematical properties and their 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 of graphs, both from a practical and a theoretical perspective, similar to the level expected from a Computer Science graduate in most curricula out there and perhaps more profound in some niche topics that are not usually taught in a CS major.NOTE: This book is a work in progress. Buying it now gives you access to the current and all future versions.