article
Some circuits in graph or network theory
Eulerian and Hamiltonian circuits are defined with some simple examples and a couple of puzzles to illustrate Hamiltonian circuits.
problem
Doodles
Age
14 to 16
Challenge level
Draw a 'doodle' - a closed intersecting curve drawn without taking pencil from paper. What can you prove about the intersections?
problem
Network trees
Age
14 to 18
Challenge level
Explore some of the different types of network, and prove a result about network trees.
problem
Magic caterpillars
Age
14 to 18
Challenge level
Label the joints and legs of these graph theory caterpillars so that the vertex sums are all equal.
problem
Stringing it out
Age
14 to 16
Challenge level
Explore the transformations and comment on what you find.
problem
Tourism
Age
11 to 14
Challenge level
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.
problem
Maximum flow
Age
16 to 18
Challenge level
Given the graph of a supply network and the maximum capacity for
flow in each section find the maximum flow across the network.
problem
Production equation
Age
16 to 18
Challenge level
Each week a company produces X units and sells p per cent of its
stock. How should the company plan its warehouse space?
problem
Flow chart
Age
11 to 14
Challenge level
The flow chart requires two numbers, M and N. Select several values
for M and try to establish what the flow chart does.
problem
Procedure solver
Age
16 to 18
Challenge level
Can you think like a computer and work out what this flow diagram
does?
problem
Zeller's birthday
Age
14 to 16
Challenge level
What day of the week were you born on? Do you know? Here's a way to
find out.
problem
Painting by numbers
Age
16 to 18
Challenge level
How many different colours of paint would be needed to paint these
pictures by numbers?
problem
Torus patterns
Age
16 to 18
Challenge level
How many different colours would be needed to colour these
different patterns on a torus?
problem
Mad robot
Age
16 to 18
Challenge level
Can you work out what happens when this mad robot sets off?
problem
Drug testing
Age
16 to 18
Challenge level
How do different drug-testing regimes affect the risks and payoffs for an athlete who chooses to take drugs?
problem
Mystery procedure
Age
14 to 16
Challenge level
Can you work out what this procedure is doing?
problem
Sorted
Age
14 to 18
Challenge level
How can you quickly sort a suit of cards in order from Ace to King?
problem
Simply graphs
Age
16 to 18
Challenge level
Look for the common features in these graphs. Which graphs belong together?
problem
Happy birthDay
Age
16 to 18
Challenge level
Can you interpret this algorithm to determine the day on which you were born?
problem
The Olympic torch tour
Age
14 to 16
Challenge level
Imagine you had to plan the tour for the Olympic Torch. Is there an efficient way of choosing the shortest possible route?