Tiny example
A tiny network
Draw four dots. Join A to B, B to C and C to D.
A can reach D, but only by travelling through B and C.
Graph theory
Studying dots and the connections between them.
In graph theory, a graph is a network. The dots are vertices and the lines are edges. The exact drawing often matters less than what connects to what.
Why it matters
Graph theory models maps, social networks, routes, conflicts, dependencies and search problems.
Things to watch for
- Confusing graph theory graphs with coordinate graphs.
- Thinking the drawing shape is always important.
- Ignoring whether connections have direction or weight.
Where it connects
discrete mathsnetworksalgorithms
Try it in a tool
ConnectionRepresentationQEDReasoning
Graph Theory Visualiser
Build a graph and step through breadth-first and depth-first search.
ExplorationConnectionOptimisationQEDReasoning
Dijkstra Visualiser
Explore weighted shortest paths, tentative distances and settled nodes.
ExplorationConnectionQEDReasoningPattern
Planarity and Map Colouring Lab
Explore planar graphs, Euler's formula, crossings and map colouring.
Exploration