Graphs: dots, lines and what they mean
A graph is dots joined by lines, and the same picture can describe friends, roads or a build order.
A graph is two things: a set of nodes (the dots) and a set of edges (the lines that join them). That is the whole definition. The power comes from what you decide the dots and lines mean, because one structure then answers questions about friends, cities, computers and tasks all at once.
Nodes and edges — what the same picture can mean: people - node = person, edge = "is friends with" family - node = person, edge = "is the parent of" maps - node = city, edge = road between them networks - node = computer, edge = cable or Wi-Fi link builds - node = task, edge = "must run after" Directed edge: A -> B is not the same as B -> A. "is the parent of" is directed. "is friends with" is not.
A tree is a graph with no loops: exactly one path leads between any two nodes, and there is always a node you can call the root. Folder structures, family trees and knock-out tournaments are all trees. As soon as a path can come back to where it started, it is not a tree any more.
Practice
Match each situation with what a node and an edge mean inside it.
Hints
- Ask what a single step between two items means in each situation.
- In a build list the arrow says what must happen first, not what is similar.
13 XP
You can walk from Tom to Ana, then from Ana to Lena, and also straight from Lena back to Tom. What is this graph?
Hints
- A tree has no loops at all — if you can walk in a circle, it is not a tree.
- In a family, you go up to a shared parent and then down again.
14 XP
Draw the build graph: the database must be ready before the API server, the cache must be ready before the API server, and the frontend must be ready before the API server. Only after the API server does the site go live.
Hints
- Draw one arrow for every "must be finished before" rule in the description.
- The machine that everything depends on sits between those three and the final step.
18 XP