Your cart is currently empty!
VCE General Maths Unit 2 AOS 2
Welcome to Graphs and Networks
This area of study introduces the fundamentals of discrete mathematics, focusing on how networks can be represented and analysed. You’ll learn the essential language of graph theory, explore the properties of different types of graphs, and apply algorithms to solve practical optimisation problems. These concepts are a critical foundation for ‘Networks and decision mathematics’ in Units 3 & 4.
Key Knowledge
- Definitions of graphs, vertices, edges, and loops
- Properties of planar graphs and Euler’s formula
- Eulerian and Hamiltonian paths and cycles
- Prim’s algorithm for minimum spanning trees
Key Skills
- Use adjacency matrices to represent graphs
- Apply Euler’s formula to solve for v, e, or f
- Determine the traversability of a graph
- Construct a minimum spanning tree
The Language of Networks
Mastering the vocabulary of graph theory is the first step to success. These terms form the building blocks for all network analysis. Click on each card to reveal its definition.
📈
Graph
📍
Vertex
↔️
Edge
🔢
Degree
🔄
Loop
✅
Simple Graph
🔗
Connected
🕸️
Complete
Select a term to learn more.
Representing Networks: Adjacency Matrices
While diagrams are visual, adjacency matrices provide a computational way to represent a graph. The matrix $M^n$ is a powerful tool, as its entries show the number of walks of length $n$ between vertices. Use your CAS calculator to perform these multiplications.
Example: Finding 2-Step Walks
Graph
A
C
B
Edges: A-B, B-C, C-A
Adjacency Matrix (M)
$\begin{pmatrix} 0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \end{pmatrix}$
Planar Graphs & Euler’s Formula
A planar graph can be drawn on a flat surface without any edges crossing. For any connected planar graph, the number of vertices ($v$), edges ($e$), and faces ($f$) are related by Euler’s Formula: $v – e + f = 2$.
Euler’s Formula Calculator
Enter any two values to find the third.
Planarity Test
A simple, connected planar graph must satisfy $e \le 3v – 6$. If this condition is NOT met, the graph is definitely non-planar.
Traversability: Eulerian vs. Hamiltonian
Can you travel along a network in a specific way? Eulerian problems focus on traversing every edge once, while Hamiltonian problems focus on visiting every vertex once. Their rules are very different.
Sample Graph
A graph with vertices A, B, C, D and edges A-B, B-C, C-D, D-A, and A-C.
Vertex Degrees:
deg(A)=3, deg(B)=2, deg(C)=3, deg(D)=2
Eulerian Paths
Travels every EDGE exactly once.
Rule:
- Circuit (ends at start): All vertices have even degree.
- Trail (ends somewhere else): Exactly two vertices have odd degree.
Hamiltonian Paths
Visits every VERTEX exactly once.
Rule:
There is no simple formula. Paths and cycles must be found by inspection and trial-and-error.
Minimum Spanning Trees
A Minimum Spanning Tree (MST) connects all vertices in a weighted graph with the lowest possible total edge weight. Prim’s Algorithm is a step-by-step method to find the MST. Click ‘Next Step’ to see the algorithm in action.
Prim’s Algorithm Simulator
A weighted graph used to find the MST.
Algorithm Trace
| Step | Edge Chosen | Weight | Total |
|---|
