The Chinese Mailman, Who Does not Like to Walk

Please check Chinese Postman Problem, and its politically correct cousin - Route Inspection Problem. They are very important to solve graph theoretic problems in bioinformatics or elsewhere.

The Chinese postman problem is a mathematical problem of Graph theory. It is also known as route inspection problem. Suppose there is a mailman who needs to deliver mail to a certain neighborhood. The mailman is unwilling to walk far, so he wants to find the shortest route through the neighborhood, that meets the following criteria:

It is a closed circuit (it ends at the same point it starts).

He needs to go through every street at least once.

If the graph traveled has an Eulerian Circuit, this circuit is the ideal solution.

That brings us to the question of how to know, whether the graph has an Eulerian circuit, and the answer is BEST theorem. It is is for directed graphs. BEST does not stand for superlative of good, better, but is an acronym for four names, with one being de Bruijn.

-————————————-

In the above context, readers may amuse themselves with the history of two influential European mathematicians - Blanche Descartes and Nicolas Bourbaki. Even though they published many scholarly books and articles on graph theory and set theory, the mathematicians did not exist.

They were two groups of mathematicians from England and France writing under pseudonym. The French group (Bourbaki) included Andre Weil and Szolem Mandelbrojt. If that Mandelbrojt name sounds familiar, he was indeed the uncle of Benoit Mandelbrot of fractal fame.

British group (Descartes) included some of the BEST people - R. Leonard Brooks, Arthur Harold Stone, Cedric Smith, and W. T. Tutte. BEST stands for de Bruijn, van Aardenne-Ehrenfest, Cedric Smith and Tutte. If that Ehrenfest name sounds familiar to physicists, she was indeed the daughter of Paul Ehrenfest.