You are currently browsing the tag archive for the ‘Chinese postman’ tag.

The Chinese Postman Problem

There is a fantastic pdf resource from Suffolk Maths which goes into a lot of detail on this topic – and I will base my post on their resource.   Visit their site for a more in-depth treatment.

The Chinese Postman Problem was first posed by a Chinese mathematician in 1962.  It involved trying to calculate how a postman could best choose his route so as to mimise his time.  This is the problem that Kuan Mei-Ko tried to solve:

chinesepost1

How could a postman visit every letter on the graph in the shortest possible time?

Solving this requires using a branch of mathematics called graph theory, created by Leonard Euler.  This mathematics looks to reduce problems to network graphs like that shown above.  Before we can solve this we need to understand some terminology:

chinesepost3

Above we have 3 graphs.  A graph which can be drawn without taking the pen off the paper or retracing any steps is called traversable (and has a Euler trail).  Graph 1 is not traversable.  Graph 2 is traversable as long as you start at either A or D, and Graph 3 is traversable from any point that you start.  It turns out that what dictates whether a graph is traversable or not is the order of their vertices.

Looking at each letter we count the number of lines at the vertex.  This is the order.  For graph 1 we have 3 lines from A so A has an order of 3.  All the vertices on graph 1 have an order of 3.  For graph 2 we have the orders (from A, B, C, D, E in turn) 3, 4, 4, 3, 2.  For graph 3 we have the orders 4,4,4,4,2,2.

This allows us to arrive at a rule for working out if a graph is traversable.

If all orders are even then a graph is traversable.  If there are 2 odd vertices then we can find a traversable graph by starting at one of the odd vertices and finishing at the other.  We need therefore to pair up any odd vertices on the graph.

Next we need to understand how to pair the odd vertices.  For example if I have 2 odd vertices, they can only be paired in one way.  If I have 4 vertices (say A,B,C,D) they can be paired in 3 different ways (either AB and CD or AC and BD or AD and BC) .  The general term rule to calculate how many ways n odd vertices can be paired up is (n-1) x (n-3) x (n-5) … x 1.

So now we are ready to actually solve the Chinese Postman Problem.  Here is the algorithm:

chinesepost4

So, we can now apply this to the Chinese Postman Problem below:

chinesepost1

Step 1:  We can see that the only odd vertices are A and H.

Step 2:  We can only pair these one way (AH)

Step 3 and 4: The shortest way to get from A to H is ABFH which is length 160.  This is shown below:

 chinesepost5

 Step 5 and 6: The total distance along all the lines in the initial diagram is 840m.  We add our figure of 160m to this.  Therefore the optimum (minimum) distance it is possible to complete the route is 1000m.

Step 7:  We now need to find a route of distance 1000m which includes the loop ABFH (or in reverse) which starts and finishes at one of the odd vertices.  One solution provided by Suffolk Maths is ADCGHCABDFBEFHFBA.  There are others!

The Bridges of Konigsburg

Graph theory was invented as a method to solve the Bridges of Konigsburg problem by Leonard Euler.  This was a puzzle from the 17oos – Konigsburg was a Russian city with 7 bridges, and the question was, could anyone walk across all 7 without walking over any bridge twice.  By simplifying the problem into one of connected lines, Euler was able to prove that this was in fact impossible.

If you like this post you might also like:

Knight’s Tour – This puzzles dates over 1000 years and concerns the ways in which a knight can cover all squares on a chess board.

Game Theory and Tic Tac Toe – Tic Tac Toe has already been solved using Game Theory – this topic also brings in an introduction to Group Theory.

Website Stats

  • 7,331,674 views

IB Maths Exploration Guide

IB Maths Exploration Guide

A comprehensive 63 page pdf guide to help you get excellent marks on your maths investigation. Includes:

  1. Investigation essentials,
  2. Marking criteria guidance,
  3. 70 hand picked interesting topics
  4. Useful websites for use in the exploration,
  5. A student checklist for top marks
  6. Avoiding common student mistakes
  7. A selection of detailed exploration ideas
  8. Advice on using Geogebra, Desmos and Tracker.

Available to download here.

IB Exploration Modelling and Statistics Guide


IB Exploration Modelling and Statistics Guide

A 60 page pdf guide full of advice to help with modelling and statistics explorations – focusing in on non-calculator methods in order to show good understanding. Includes:

  1. Pearson’s Product: Height and arm span
  2. How to calculate standard deviation by hand
  3. Binomial investigation: ESP powers
  4. Paired t tests and 2 sample t tests: Reaction times
  5. Chi Squared: Efficiency of vaccines
  6. Spearman’s rank: Taste preference of cola
  7. Linear regression and log linearization.
  8. Quadratic regression and cubic regression.
  9. Exponential and trigonometric regression.

Available to download here.

Recent Posts

Follow IB Maths Resources from British International School Phuket on WordPress.com