Introduction
A graph is a set of vertices connected by edges. That’s it — the whole thing.1
What makes it interesting is that this minimal structure shows up everywhere: social networks, road maps, dependency trees, the note you’re reading right now.2
Basic Concepts
Vertices
A vertex is the fundamental unit — sometimes called a node.3 Every graph-theoretic structure ultimately bottoms out at vertices and edges, even when the surface presentation looks very different (matrices, sets of pairs, visual diagrams).
Labeled vs Unlabeled
Canonical Forms
Degree
The degree of a vertex is how many edges touch it.4
In-Degree and Out-Degree
Edges
Directed vs Undirected
Weighted Edges
Positive and Negative Weights
Negative weights are where most of the interesting algorithmic trouble starts.5 Shortest-path problems that are trivial with positive weights become NP-hard if you allow arbitrary negatives — the “shortest path” can dip through a negative cycle infinitely.
Multi-Edges and Self-Loops
Paths and Walks
Simple Paths
Cycles
Types of Graphs
Trees
A tree is a connected graph with no cycles.6
Binary Trees That Are Deliberately Very Long So You Can See How Wrapping Looks In A Deeply Nested Outline Entry
Spanning Trees
Cycles
Bipartite Graphs
Complete Graphs
Planar Graphs
Planar graphs are graphs you can draw without edges crossing.7 Kuratowski’s theorem pins down exactly when this is possible: a graph is planar iff it contains no subgraph topologically equivalent to either or .
Graph Representations
Adjacency Matrix
An matrix where iff there’s an edge from to .8
Adjacency List
Edge List
Incidence Matrix
Common Algorithms
Traversal
Breadth-First Search
Depth-First Search
Shortest Path
Dijkstra
Dijkstra’s algorithm finds the shortest path from a source to every other vertex — but only for non-negative edge weights.9 The classical version runs in with a binary heap; Fibonacci heaps bring it down to in theory, though the constants are bad enough that you rarely see them used in practice.
Bellman-Ford
Floyd-Warshall
Minimum Spanning Tree
Kruskal
Prim
Maximum Flow
Ford-Fulkerson
Edmonds-Karp
Topological Sort
Strongly Connected Components
Applications
Social Networks
Road Networks
Dependency Graphs
Neural Networks
Further Reading
Books
Papers
Online Resources
Things worth knowing
- A path is a sequence of edges that connects two vertices.
- A graph is connected if there’s a path between any two vertices.
- A tree is a connected graph with no cycles — which makes it the simplest interesting graph.
The tools for reasoning about graphs come from linear algebra — specifically, the adjacency matrix turns graph problems into matrix problems, and suddenly eigenvalues have something to say about connectivity.10
Footnotes
-
Often traced to Euler’s 1736 paper on the Seven Bridges of Königsberg — a problem that asked whether one could walk through the city crossing each bridge exactly once. ↩
-
The internet is a graph. The citation structure of scientific papers is a graph. Your contacts list is (implicitly) a graph. ↩
-
Different fields disagree: computer science uses “node”, mathematics uses “vertex”, network science often uses both interchangeably. ↩
-
The sum of all vertex degrees equals twice the edge count — a fact whimsically called the handshaking lemma. ↩
-
Dijkstra’s algorithm breaks when negative weights are present. Bellman-Ford handles them but runs slower. ↩
-
Equivalently: a connected graph with exactly edges, where is the number of vertices. ↩
-
The classic example of a *non-*planar graph is , the complete graph on 5 vertices — you can’t draw it without at least one edge crossing. ↩
-
For undirected graphs this matrix is symmetric. Its eigenvalues carry a surprising amount of information about the graph’s structure. ↩
-
The algorithm was conceived in 1956 — Dijkstra famously designed it in about 20 minutes while sitting in a café. ↩
-
This is the entry point to spectral graph theory, which is a whole rabbit hole. ↩