Things and the Links Between Them

A graph is points and connections, and almost every network question becomes easy once the two decisions about direction and cost have been made honestly.

The same picture, over and over

A road map, a dependency list, a friends network, the pages of a website, the

states a payment can be in. These have nothing in common except their shape,

and the shape is this: there are things, and some pairs of things are

connected.

Write that down and nothing else. Each thing becomes a point. Each connection

becomes a link between two points. A road loses its surface, its length and

its name, and becomes a link between two towns. A person loses everything

except their identity. This is a deliberately poor description and it is the

whole trick: what survives the discarding is the part that every question

about reachability, distance and ordering depends on, and once a situation is

written this way, the question being asked is almost always one of four

standard walks that the rest of this course derives.

FIG 1What survives when a road map becomes a graph

The model keeps the identities, the pairings, and at most one number per link. Everything else about a road is thrown away, and the standard walks still answer the question.

The first decision: does a link work both ways

A road between two towns usually works both ways, and a one way street does

not. Friendship on most networks is mutual and following is not. A task that

depends on another task is a connection with an unmistakable direction.

If the links have direction, the graph is called directed, and a link from $u$

to $v$ says nothing at all about getting from $v$ to $u$ . If they do not, each

link can be walked either way. The decision has to be made from the situation

rather than from convenience, because getting it wrong is silent. A model that

treats following as mutual will report that a message can travel from one

account to another when there is no route at all, and nothing in the

arithmetic will complain. The answer will simply be wrong.

The honest test is to pick one link and ask whether both halves are true. Can

traffic go from the first town to the second, and can it come back? If the

answer differs, the graph is directed, even if most of its links happen to

work both ways. A two way street in a directed graph is written as two links,

one in each direction, which costs nothing and keeps the model truthful.

The second decision: do links cost different amounts

A graph where every link is the same answers the question how few links. A

graph where links carry a number answers the question how cheap. Both are

useful and they are not the same question.

A route with three long motorway stretches may be faster than one with five

short town roads. The first is better by cost and the second is better by

count, and only one of them is the answer to what the traveller asked. So the

number attached to a link has to measure the thing that the question is about:

minutes if the question is about time, money if it is about money, hops if it

is about hops.

FIG 2Four familiar situations, modelled

	points	links	directed	weighted
road network	1	1	0	1
social following	1	1	1	0
task dependencies	1	1	1	0
web pages	1	1	1	0

A one in the directed column means the link has a direction, and a one in the weighted column means it carries a cost. The road network is the only one of the four that needs weights, and the only one where most links work both ways. The marked cells are the two decisions this lesson is about.

How big is a graph

A graph has two sizes, not one, and every cost in this course is written in

terms of both. Call the number of points $n$ and the number of links $m$ .

They are not related by any fixed rule. A graph of $n$ points can have as few

as zero links and as many as roughly $n^2$ of them, and real graphs live all

over that range. A road network has a handful of roads per junction, so $m$ is

a small multiple of $n$ . A graph of who has ever messaged whom in a small

office may have nearly every pair connected, so $m$ is close to $n^2$ .

FIG 3The two sizes and the range between them

: the number of points
: the number of links

The upper bound counts every pair once, which is the most links an undirected graph can have without repeating one. Whether a graph is sparse or dense decides which of the two storage methods in the next lesson is right, and it changes the cost of every walk in this course.

A graph with a million points and two million links is a different object from

one with a million points and a thousand million links, even though both have

a million points. The first fits in memory comfortably and the second does

not. Quoting only $n$ hides that difference, which is why nothing in this

course is described as costing a function of $n$ alone.

FIG 4The same two decisions, written down

python

roads = {"ashby": {"bexley": 12, "canton": 30}, "bexley": {"ashby": 12}}  # undirected, weighted: both halves present
follows = {"ana": {"bo", "cy"}, "bo": set()}  # directed, unweighted: ana reaches bo, bo does not reach ana
n = len(follows)
m = sum(len(outgoing) for outgoing in follows.values())
print(n, m, m / (n * n))  # 2 2 0.5, which is dense, because the graph is tiny

The undirected graph stores each link twice, once from each end, which is what makes it undirected in practice. The directed one stores it once. Counting the links and dividing by the square of the points gives the density, and the number only means something on a graph large enough for the ratio to settle.

Where the modelling goes wrong

Three mistakes account for most of the bad answers in this subject, and all

three happen before any walking starts.

The first is treating a directed situation as undirected, usually because the

data arrived as a list of pairs with no direction recorded. The result is a

model that finds routes nobody can travel.

The second is attaching a weight that does not measure what the question is

about. A delivery network weighted by distance will not produce the fastest

route if the slow part is loading rather than driving.

The third is choosing the wrong thing to be a point. If a railway network is

modelled with stations as points, a route that requires changing trains looks

identical to one that does not, because the change is not represented

anywhere. Making a point out of each platform rather than each station puts

the change back into the model as a link with a cost, and the answers become

right. The lesson on wide questions at the end of this course returns to this,

because the choice of what counts as a point is the only genuinely creative

part of using graphs, and the rest is mechanical.

Recap

A graph is nothing more than a set of things and a set of connections between pairs of them, which is why so many unrelated situations turn out to be the same picture.
Two decisions fix the model: whether a connection works both ways, and whether connections differ in cost.
Getting those two decisions wrong produces answers that look reasonable and are not, which is the most common failure in this whole subject.

This is the reading half

Starting the course gives you your own copy of it. Every idea on every page has problems standing under it, marked with a reason rather than a tick, and any sentence you do not believe can be opened and argued with. None of that can happen on a page nobody owns.

The contents

NextWriting a Graph Down →