The world drawn with dots and lines: graphs

A dot is a thing

A graph starts with dots.
One dot is one thing.
A station, a person, a web page,
anything can be a dot.
We give each dot a name.
That's how we know which is which.
No lines yet.
Just dots, scattered about.

Tap an empty spot to place a dot. One dot is one thing. (dot = node)

The more dots you placed,
the more things there were.
But dots alone
are just scattered specks.
Stations sitting apart
aren't a route map.
What's missing is how
the dots connect to each other.
Let's draw that connection next.

A line is a relationship

Now let's link the dots.
Joining two dots with a line
means "these two are related."
There's a path between two stations,
two people are friends,
this web page links to that one.
One line is one relationship.
Dots and lines together make a graph.

Tap one dot, then another, and a line appears. One line is one relationship. (line = edge)

The more lines you drew,
the more the dots wove together.
Scattered dots
at last became a route map.
Dots are things, lines are relationships.
With just these two
you can draw countless things in the world.
And a shape we know is hiding among them.

A tree is a special graph

A graph can form a loop.
Start at dot A,
follow the lines,
and if you come back to A, that's a loop.
A graph with no loop at all,
that is exactly a tree.
No way back,
just branching out like limbs.
So a tree is one kind of graph.

Tap the line that makes a loop to cut it. Remove the loop and it becomes a tree. tree is part of graph.

Cut one loop
and the way back vanished.
The graph that looked tangled
became a clean tree.
The folders and family trees we saw before
were exactly trees like this.
A tree is the special case of a graph,
so the graph is the bigger umbrella.

Graphs are everywhere

Put on the glasses of dots and lines
and the world looks different.
A subway is stations (dots) and lines (lines),
a friend network is people (dots) and friendship (lines).
The web is pages (dots) and links (lines).
Things that look completely different
were really the same picture.
So solve one
and the rest solve too.

Tap to switch examples. Subway, friend network, web, all the same dots and lines.

Even when the example changed,
the skeleton of the picture stayed the same.
Dots are things, lines are relationships.
Only the labels change.
That very fact
makes graphs truly useful.
With one tool
you can draw countless problems in the world.

Let's wrap up

Gathered on one line, it's this.
Dots are things, lines are relationships.
A picture drawn with dots and lines is a graph.
A special graph with no loop is a tree.
Subways, friend networks, the web,
all can be drawn with dots and lines.
Now that the dots and lines are laid out,
one question remains.
How do we move around among these dots?

Tap the key points in order to review. (dot=thing → line=relationship → graph → tree is a graph with no loop)

Now that you can draw a graph,
the real fun starts here.
How to start at one dot
and visit every dot along the lines,
how to find the nearest dot.
That's called graph traversal.
Next lesson, let's follow together
how we roam over the dots and lines.