The vocabulary of graphs

Graph problems are stated in a small vocabulary, and reading a problem quickly depends on knowing it. The picture below is six colleagues; an edge joins two people who have worked on a project together.

A node (or vertex) is one item: a person, a currency, a cell of a grid. An edge joins two nodes. Two nodes joined by an edge are adjacent, and each is a neighbour of the other. By convention n is the number of nodes and m (sometimes E) the number of edges; every complexity in this chapter is written in those two letters.

An undirected edge works both ways: if A has worked with B, B has worked with A. A directed edge has a start and an end and can be followed only one way: following someone on a social network, a payment from one account to another, a course that must be taken before another.

In code an undirected edge is almost always stored as two directed ones, u → v and v → u. Forgetting the second is one of the most common bugs in a graph solution.

The degree of a node is the number of edges that touch it. In the team graph E has worked with four people, so its degree is 4.

Every edge has two ends, so it adds one to the degree of each. The degrees therefore always add up to exactly twice the number of edges (here 2 + 3 + 2 + 2 + 4 + 1 = 14 = 2 × 7). Two consequences come up in puzzles: the number of nodes with odd degree is always even, and a graph in which every node has degree d has exactly n·d / 2 edges.

For a directed graph, degree splits in two. The in-degree of a node counts edges arriving at it; the out-degree counts edges leaving it. In a follow network, in-degree is the number of followers and out-degree the number of accounts followed.

In-degree is the quantity behind topological sorting: a task with in-degree zero has nothing left to wait for, so it can start. Summed over all nodes, the in-degrees and the out-degrees each equal the number of edges.

A path is a sequence of nodes in which each consecutive pair is joined by an edge, with no node repeated. Its length is the number of edges, or, in a weighted graph, the sum of their weights. A cycle is a path that returns to its first node.

Whether a graph has a cycle decides which algorithms apply. A directed graph without cycles can be put in an order that respects every edge; one with a cycle cannot. A connected undirected graph without cycles is a tree, with exactly n − 1 edges.

An undirected graph is connected if every node can reach every other. If it cannot, it splits into connected components: maximal groups of nodes that can all reach one another, with no edge between groups.

Counting islands in a grid, grouping accounts that share an email address, and finding friend circles are all the same question: how many components are there, and which nodes are in each? For a directed graph the matching idea is a strongly connected component, a group in which every node can reach every other by following the arrows.

A quick check that pays off: a graph with n nodes and m edges has at least n − m components. With fewer than n − 1 edges it cannot possibly be connected.