Kaliningrad is a Russian seaport named for a Soviet revolutionary. It sits near the Baltic Sea, between Poland and Lithuania, and it's a place where pre-Putin Russian leaders would occasionally threaten to install nuclear missiles. But in the 18th century, it was a city called Königsberg in the German kingdom of Prussia. And it was a math problem.
Königsberg stretched across both banks of the river Pregel, and it included two islands in the middle of the river. Seven bridges connected these islands and the rest of Königsberg, and for years, people wondered if they could walk across all seven bridges without crossing any of them more than once.
Then, in 1736, the Swiss mathematician Leonhard Euler (pronounced oiler) showed it was impossible. The trouble was that each landmass---the two islands and the two river banks---were touched by an odd number of bridges. If each was touched by an even number, a continuous walk across all the bridges would have been doable. Euler called his work Geometriam Situs, or the Geometry of Place, and it was the beginning of what we now call graph theory. After many years, with Prussia vanishing and Königsberg morphing into Kalingrad and the Soviet Union giving way to Putin's Russia, it produced an app from Google.
This week, Google unveiled a smartphone app that helps you plan your vacations. It's called Trips, and among other things, it will automatically plan sightseeing trips through the world's big cities. You tell it you'll be in Paris for eight hours, and it maps out a path from one notable sight to another, giving you just enough time to enjoy one before moving to the next. It does this with two things: scads of online data showing sightseeing visits by others in the past, and Euler's Geometry of Place.
"If you know the places you want to visit, you can use algorithms built on top of Euler to figure out the best route," says Google researcher Andrew Tomkins, who worked on the project. "Euler is a sub-routine for our itinerary work."
In recent years, Google and other Internet operations like Facebook and Amazon have changed the way we live through the analysis of massive amounts of data. Inside Google Research, Tomkins was also part of the team that built Smart Reply, a Gmail tool that has learned to automatically respond to emails by analyze millions of existing replies, and so many others are doing similar work with not only email messages, but photos and spoken words and even computer viruses and targeted ads. But it's worth remembering that none of this is magic---not even the deep neural networks that are built in the image of the human brain. At the bottom of it all, this is just good old fashioned math. Sometimes, it's 280-year-old math.
Under the covers, Trip does make use of neural networks, which is really just very complex linear algebra. But the more important player is graph theory. In graph theory, the Königsberg bridges are called edges and the landmasses are called nodes, and Google can apply this model to the cities where Trips maps out your daily sightseeing. The sights are the edges, and the roads between them are the nodes. Again, the basic problem is: can you visit all the edges without visiting any of them more than once? It's a matter of even edges versus odd.