Represent situations with graphs and networks, use terminology and matrices, and solve shortest path, minimum spanning tree and connection problems.

What this dot point is asking

You need to draw and interpret graphs, count edges and degrees, build adjacency matrices, classify walks, trails and paths, and apply the standard network algorithms for connection and routing problems.

Graph terminology

A graph is a set of vertices (nodes) joined by edges. The degree of a vertex is the number of edge ends meeting at it. A graph is connected if you can travel between any two vertices. A weighted graph (network) attaches a number such as distance, cost or time to each edge.

Adjacency matrices

An adjacency matrix records the number of edges directly joining each pair of vertices. For an undirected graph the matrix is symmetric. A diagonal entry of $2$ records a single loop (it contributes $2$ to the degree).

Euler and Hamilton

An Eulerian trail uses every edge exactly once; it exists only if the graph is connected and has exactly $0$ or $2$ odd-degree vertices. If it has $0$ odd vertices the trail closes into an Eulerian circuit. A Hamiltonian path visits every vertex exactly once.

Minimum spanning tree

A spanning tree connects all $n$ vertices with exactly $n-1$ edges and no cycles. The minimum spanning tree (MST) is the spanning tree of least total weight, used to connect sites (cable, pipe, road) as cheaply as possible.

Shortest path

The shortest path between two vertices is the route of least total weight. For small networks you find it by inspection: list the possible routes, total the edge weights, and choose the smallest. Always check more than one route, because the fewest-edges route is not always the lightest.

Directed graphs and flow

In a directed graph (digraph) each edge has an arrow giving allowed direction; the adjacency matrix is then not symmetric. Directed networks model precedence (which task must precede another) and one-way flow.