A Free Graph Theory Textbook That Teaches Through Puzzles and Proofs

I've been doing a lot with graphs over the past couple of years. Basically since I started using neo4j, although not everything involves neo4j directly. I've developed a number of really interesting graph algorithms, but I'm always a bit disappointed by how little use I get out of my graph theory knowledge. I've never needed a Hamilton path or do something with the degrees of my vertices. It's all just logic and intuition.

But maybe I should read this to see if there's anything that applies to my current work.

I’ve been using graph theory for years professionally. A good example of practical uses of graph theory is any routing software. It is basically graphs all the way down.

For starters the whole street network is represented as a directed graph. The most widely used algorithm is the venerable A* to find paths through the vertices of the graph, not necessarily the shortest distance but the most optimal distance given all the trade-offs you wish based on the heuristics you define. There are lots of variations of A* and today most implementations would use its faster cousin: bidirectional A* which attacks the point-to-point calculation from both ends at the same time.

Then you have Dijkstra which is used for flood searches to e.g. give the best cost back home from every vertex so you know when to turn back the search if you have a search budget.

Menger’s theorem I’ve used in order to determine whether we can create a loop back. Basically search outwards, then search back without visiting those same edges.

Tarjan to ensure we identify all subnetworks so we don’t get stuck in a disconnected island of vertices with no way out to join the wider network.

A lot of these algorithms were conceived decades ago and are still the backbone of modern routing software.

One thing that’s constantly been in the back of my mind is, since routing is a highly deterministic problem space, it doesn't seem plausible that LLMs can take this over. It seems to me that it's a good example of a tool that LLM […]

Beautiful website and a breath of fresh air compared to the gitbook/vitepress typical styles these sorts of textbooks often go for.

Graphs are fantastic - PageRank [1] that powered Google Search (still does to some extent), TextRank for extractive text summarisation [2], Louvain for neighbourhood detection [3] all use graphs, as well as tonnes of others like belief propagation, Markov clustering, A*, and so on. So yeah, learn it.

[1] https://en.wikipedia.org/wiki/PageRank

[2] https://aclanthology.org/W04-3252.pdf

[3] https://en.wikipedia.org/wiki/Louvain_method

Cool. I am applying to jobs and it seems graph theory is popular in the "Leet Code" questions pace. So very timely, thank you! And clever domain name :)

One very very useful but underused[1] application of graph theory (and its application of network theory): parts data systems' configuration management.

In a hardware manufacturing setting, particularly a new or "garage" sort of shop doing lots of new business, you quickly get into a nightmare scenario of "Too Many Configurations" running headfirst into the problem of "People Are Buying Too Much of Our Stuff". As a garage shop you can do OK making five or six units of all kinds, but once the orders for 1000, 10000 start coming in, you will be torpedoed by the complexity of keeping all those lines operational. Eventually you'll screw something up, and get dinged or even blacklisted (a big deal in Defense).

But it's a problem that can be steered around by applying some graph theory to the parts data system. Some PDMs actually do this natively - Oleg Shilovitsky's OpenBOM; Yoann Maingon's Ganister, both smart guys buy their stuff! - but this network theory can be used as a reporting layer on top of any big dumb PDM.

Examples include:

(Asciidoc table from a previous slide I've used, sorry)

|===

| Method | Primary Use

| In-degree centrality | Shared/high-risk components

| Out-degree centrality | Complex assemblies

| Betweenness centrality | Change risk

| Closeness centrality | Architectural centrality

| PageRank | Strategic component

| Degree distribution | Architecture health / power law check

| Connected components | Find orphans

| Sh […]

https://vertex.degree/beginning/degrees#the-hypercube-graphs

I remember to this day the exact location I was when being introduced to construct hypercubes, to the exact bench in our uni cafeteria. It changed my understanding of multidimensionality completely.