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) |
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.
