Finding patterns in complex cycles

Ireland’s greatest mathematician, William Rowan Hamilton, has an important part to play in the Young Scientist project submitted by Paul Clarke.

It involves an investigation into what are known as “Hamiltonian cycles”, something mathematicians study within graph theory. Hamiltonian cycles, however, are very easy for the non-mathematicians among us to understand.

Simple examples involve walking through a city and crossing each of its bridges only once, or the famous Dublin challenge: travelling from north city to south city without walking directly past a pub.

“A Hamiltonian cycle is a path along a graph that visits each point connected by vectors but only once,” explains Paul (16), from St Paul’s College, Dublin. Finding the route is simple if there are only a few points involved but rapidly becomes very difficult the more points that must be visited.

No backtracking

He gives as an example of visiting each of Ireland’s 32 counties just once without backtracking. The “brute force” computational approach could be used, with each potential path being tested one by one, but the possible number of route options “could get unimaginably large” very quickly, he says. It took a computer able to process graph theory problems 56 minutes of running time to show there were 145,346 possible routes to take for this problem.

Clarke assumed there must be another way and decided to examine non-computational methods. He developed ways to analyse a complex graph and found patterns emerged, allowing him to develop a new formula to solve graph problems.

The formula needed further development, however, “and will take another theoretical advance” to complete the method, something he hopes to have ready for the 2014 Young Scientist competition.

The work isn’t just about the maths. Graph theory solutions are useful in computer and communication technology, in modelling molecules and in biochemistry to describe how proteins fold into their finished shapes, he added.