Networks/graph theory

There are 45 NRICH Mathematical resources connected to Networks/graph theory
Travelling Salesman
problem

Travelling salesman

Age
11 to 14
Challenge level
filled star empty star empty star
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?
Magic Caterpillars
problem

Magic caterpillars

Age
14 to 18
Challenge level
filled star filled star filled star
Label the joints and legs of these graph theory caterpillars so that the vertex sums are all equal.
Tourism
problem

Tourism

Age
11 to 14
Challenge level
filled star filled star filled star
If you can copy a network without lifting your pen off the paper and without drawing any line twice, then it is traversable. Decide which of these diagrams are traversable.
Plum Tree
problem

Plum tree

Age
14 to 18
Challenge level
filled star empty star empty star
Label this plum tree graph to make it totally magic!
The Bridges of Konigsberg
problem

The bridges of konigsberg

Age
11 to 18
Challenge level
filled star empty star empty star
Investigate how networks can be used to solve a problem for the 18th Century inhabitants of Konigsberg.
Olympic Magic
problem

Olympic magic

Age
14 to 16
Challenge level
filled star filled star empty star

in how many ways can you place the numbers 1, 2, 3 … 9 in the nine regions of the Olympic Emblem (5 overlapping circles) so that the amount in each ring is the same?

Cube Net
problem

Cube net

Age
16 to 18
Challenge level
filled star filled star empty star
How many tours visit each vertex of a cube once and only once? How many return to the starting point?
Magic W
problem

Magic w

Age
14 to 16
Challenge level
filled star filled star empty star

Find all the ways of placing the numbers 1 to 9 on a W shape, with 3 numbers on each leg, so that each set of 3 numbers has the same total.

Maximum Flow
problem

Maximum flow

Age
16 to 18
Challenge level
filled star empty star empty star
Given the graph of a supply network and the maximum capacity for flow in each section find the maximum flow across the network.
Knight Defeated
problem

Knight defeated

Age
14 to 16
Challenge level
filled star empty star empty star
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?