Graphs and networks · Grade 12
In Grade 12 you learn: shortest paths and trees.
A graph is a set of points (vertices) joined by lines (edges). Graphs model road maps, social networks, circuits and timetables. Graph algorithms find shortest routes, cheapest connecting networks and efficient delivery rounds.
Key facts
- The degree of a vertex is the number of edges meeting it. The degrees always add up to twice the number of edges.
- A tree is connected with no cycles. A tree with n vertices has n − 1 edges. The complete graph Kₙ has (n(n − 1))/2 edges.
- Eulerian (a closed trail using every edge once): every degree is even. Semi-Eulerian: exactly two odd vertices.
- Dijkstra’s algorithm finds shortest paths. Kruskal’s and Prim’s algorithms find a minimum spanning tree.
- Route inspection with two odd vertices: add the shortest path joining them to the total edge weight.
- A connected planar graph satisfies Euler’s formula V − E + F = 2.
Worked examples
Example 1
Find a minimum spanning tree for the network shown and its total weight.
Answer: BC, AC, DE, BD: total 13
Example 2
Use Dijkstra’s algorithm to find the shortest route from A to E in the same network.
Answer: 10, along A → C → E