Networks/graph theory

Given probabilities of taking paths in a graph from each node, use matrix multiplication to find the probability of going from one vertex to another in 2 stages, or 3, or 4 or even 100.

Label this plum tree graph to make it totally magic!

The knight's move on a chess board is 2 steps in one direction and one step in the other direction. Prove that a knight cannot visit every square on the board once and only (a tour) on a 2 by n board for any value of n. How many ways can a knight do this on a 3 by 4 board?

Show there are exactly 12 magic labellings of the Magic W using the numbers 1 to 9. Prove that for every labelling with a magic total T there is a corresponding labelling with a magic total 30-T.

The graph represents a salesman’s area of activity with the shops that the salesman must visit each day. What route around the shops has the minimum total distance?

A Hamiltonian circuit is a continuous path in a graph that passes through each of the vertices exactly once and returns to the start. How many Hamiltonian circuits can you find in these graphs?

Given the graph of a supply network and the maximum capacity for flow in each section find the maximum flow across the network.

Think about the mathematics of round robin scheduling.

Explore creating 'factors and multiples' graphs such that no lines joining the numbers cross