Can every machine reach every other?
A graph is a set of points joined by lines, and it is the standard way to describe a network. Computers, roads and friendships are all graphs.
A technician must know if a cable fault cuts one machine off. This lesson shows how to describe a network as a graph and how to find out if a path exists between two machines.
By the end of this lesson
Note
I can describe a network as a graph and find a path.
Key words
| Word | What it means |
|---|---|
| Vertex | a point in a graph, such as a machine |
| Edge | a line joining two vertices, such as a cable |
| Degree | the number of edges at a vertex |
| Path | a trail of edges from one vertex to another |
| Connected | a path exists between every pair of vertices |
| Tree | a connected graph with no loop |
The cells students fill in are left blank in this preview.
A graph is vertices joined by edges
Take five machines, A to E. The machines are vertices. Each cable is an edge. A cable joins A and B, A and C, B and C, C and D, and D and E.
The degree of a machine is how many cables plug into it. Add up all the degrees and you get twice the number of edges, because every edge has two ends.
Worked example: the degree of each machine
| Machine | Cables to | Degree |
|---|---|---|
| A | B, C | 2 |
| B | A, C | 2 |
| C | A, B, D | 3 |
| D | C, E | 2 |
| E | D | 1 |
| Total | 10 = 2 x 5 edges |
The cells students fill in are left blank in this preview.
Count the degrees by program
python3 -c "e = 'AB AC BC CD DE'.split(); print([sum(x in p for p in e) for x in 'ABCDE'], len(e), 2 * len(e))"Shown here, not run. Create a free account to press Run and type it into your own lab’s terminal.
A path joins two vertices through edges
A path from A to E is a trail of edges: A to C, C to D, D to E. It has length 3, the number of edges.
A graph is connected when a path exists between every pair of vertices. To test it, start at one vertex, visit its neighbours, then their neighbours, and see if you reached everything.
Worked example: spreading out from A
| Step | New machines reached | All reached so far |
|---|---|---|
| 0 | A | A |
| 1 | B, C | A, B, C |
| 2 | D | A, B, C, D |
| 3 | E | A, B, C, D, E |
The cells students fill in are left blank in this preview.
Try it: spread out from A
network = {"A": ["B", "C"], "B": ["A", "C"], "C": ["A", "B", "D"], "D": ["C", "E"], "E": ["D"]}
seen = ["A"]
queue = ["A"]
while len(queue) > 0:
here = queue.pop(0)
for next_stop in network[here]:
if next_stop not in seen:
seen.append(next_stop)
queue.append(next_stop)
print("reached from A:", seen)
print("connected:", len(seen) == len(network))
# Take "D" out of the list for "C" and "C" out of the list for "D".
# Press Run again. What is reached now?
A common mistake
Warning
Many people think connected means every vertex has a cable to every other. It does not. It means a path exists, possibly through other vertices. In the network above, A and E share no cable, yet a path joins them.
A tree is connected with no loop
A tree is a connected graph with no loop. Remove any one edge and it falls into two pieces.
A tree of n vertices has exactly n - 1 edges. That gives a fast test. Our network has 5 vertices and 5 edges, so it is not a tree: A, B and C form a loop.
Worked example: is it a tree?
| Graph | Vertices | Edges | Connected? | A tree? |
|---|---|---|---|---|
| A-B, B-C, C-D | 4 | 3 | Yes | Yes |
| The five-machine network | 5 | 5 | Yes | No: it has a loop |
| A-B, C-D | 4 | 2 | No | No: two pieces |
| A-B, B-C, A-C, and D alone | 4 | 3 | No | No: 3 edges but D is cut off |
The cells students fill in are left blank in this preview.
Compare vertices minus one with edges
python3 -c "print(5 - 1, len('AB AC BC CD DE'.split()))"Shown here, not run. Create a free account to press Run and type it into your own lab’s terminal.