Networks and graphsIB MYP Maths Extended: Revision notes

A network (graph) is made of vertices (also called nodes) joined by edges (also called arcs). Towns and roads, computers and cables, and islands and ferries are all examples. The degree of a vertex is the number of edges that meet there. For a network with edges $AB$, $AC$, $AD$, $BC$: $A$ has degree 3, $B$ and $C$ have degree 2 and $D$ has degree 1. Every edge has two ends, so the sum of all the degrees is twice the number of edges: $3+2+2+1=8=2\times4$. This means the number of odd-degree vertices is always even.

A path is a route along edges that does not visit any vertex more than once. A network is connected if there is a path between every pair of vertices. To count the paths from one vertex to another, list them in order: choose the first step, then follow every branch. For the road network with $PQ,PR,QR,QS,RS,RT,ST$ there are 7 paths from $P$ to $T$: $PQRT$, $PQRST$, $PQST$, $PQSRT$, $PRT$, $PRST$ and $PRQST$. Listing systematically stops you missing paths or repeating them.

In a weighted network each edge has a number (its weight), such as a distance in km, a time or a cost. The length of a path is the sum of the weights of the edges it uses. To find the shortest path, work out the length of each possible path, or build up the shortest distance to each vertex step by step. From $P$ to $T$ in the road network: $PQRST=4+2+3+5=14$, $PQRT=15$, $PQST=15$, $PRST=15$, $PRT=16$. The shortest path is $PQRST$ with length 14 km. The route with the fewest edges is not always the shortest. $PRT$ has the fewest edges but is longer than $PQRST$.

An adjacency matrix records which vertices are joined. For vertices in a fixed order, the entry in row $i$ and column $j$ is $1$ if there is an edge between them and $0$ if not. It is symmetric, and each row total is the degree of that vertex. For edges $AB,AC,AD,BC$: $\begin{pmatrix} 0 & 1 & 1 & 1 \\ 1 & 0 & 1 & 0 \\ 1 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 \end{pmatrix}$ Writing the matrix as $\mathbf M$, each entry of $\mathbf M^2$ counts journeys of exactly two edges between two vertices (a vertex may be revisited, e.g. $C\to A\to C$). For the ferry network with edges $AB,AC,BC,CD$, the $C$ to $C$ entry of $\mathbf M^2$ is $3$: via $A$, via $B$ and via $D$. Higher powers $\mathbf M^n$ count journeys of exactly $n$ edges.

An Euler trail uses every edge exactly once. An Euler circuit is an Euler trail that returns to its start. Use the degrees:

• all vertices even: an Euler circuit exists (start anywhere)
• exactly two odd vertices: an Euler trail exists, starting at one odd vertex and ending at the other
• more than two odd vertices: no Euler route A Hamiltonian path visits every vertex exactly once, and a Hamiltonian cycle also returns to the start. There is no simple degree test for these, so look for a route by trying. Example with edges $AB,AC,BC,CD$: odd vertices are $C$ (degree 3) and $D$ (degree 1), so an Euler trail exists, e.g. $C\to A\to B\to C\to D$. A Hamiltonian path is $D\to C\to A\to B$, but there is no Hamiltonian cycle because $D$ has only one edge.