A network (or graph) is a set of vertices (nodes) connected by edges (arcs or links). Networks model real-world systems: roads, pipelines, project tasks, communication systems.
| Term | Meaning |
|---|---|
| Vertex (node) | A point in the network |
| Edge (arc) | A connection between two vertices |
| Weight | A value assigned to an edge (distance, time, cost) |
| Degree | Number of edges at a vertex |
| Walk | A sequence of vertices connected by edges (can repeat) |
| Path | A walk with no repeated vertices |
| Circuit/Cycle | A closed path (returns to start) |
$$\text{sum of all degrees} = 2 \times \text{number of edges}$$
This is because each edge contributes 1 to the degree of each of its two endpoints.
If vertex $A$ has edges to $B$, $C$, and $D$, then $\deg(A) = 3$.
A delivery network has 4 depots: $P$, $Q$, $R$, $S$ with roads:
- $P$–$Q$ (10 km), $P$–$R$ (15 km), $Q$–$R$ (8 km), $Q$–$S$ (12 km), $R$–$S$ (6 km)
Total edges = 5. Sum of all degrees $= 2 \times 5 = 10$.
Degrees: $\deg(P) = 2$, $\deg(Q) = 3$, $\deg(R) = 3$, $\deg(S) = 2$. Check: $2+3+3+2 = 10$. Correct.
Decision mathematics uses networks to make optimal choices:
- Shortest path: minimise distance/cost/time
- Minimal spanning tree: connect all vertices with minimum total weight
- Critical path: find the longest path in a project network (determines minimum project duration)
KEY TAKEAWAY: Every network problem begins with correct identification of vertices, edges, and weights. Drawing a clear labelled diagram before applying any algorithm is essential.
VCAA FOCUS: VCAA tests network vocabulary in short-answer questions. Know the difference between a walk, path, and circuit, and be able to calculate vertex degrees.
