In 1736 Euler solved the following problem: the city of Königsberg is set on both sides of the Pregel river and on two islands between them. There are bridges connecting the various landmasses; is it possible to walk around the city in such a way that you cross each bridge exactly once? The answer is no; (the network of landmasses and bridges in) Königsberg didn't have an Eulerian path. In order to have an Eulerian path the graph corresponding to this network must have zero or two nodes of odd degree; that is, if we consider the number of bridges on each landmass, exactly zero or two of these numbers can be odd. In Königsberg all four degrees were odd.
But the bridges were bombed in World War II, the city was renamed Kaliningrad, and only five of them were rebuilt. These are bridges connecting each of the islands to each of the shores, and a brige connecting the two islands. As you can see, there are three bridges on each island and two on each shore of the river; two of these numbers are odd, so there exists an Eulerian path. It's still somewhat useless, because you have to start on one island and end on the other.
Here's a map of the route, from Microsiervos (in Spanish), and here are some pictures that some folks took when they were visiting Kaliningrad and actually doing this.
I also remember once seeing the analogous network for New York City (the relevant landmasses being Manhattan, Long Island, Staten Island, the Bronx, and New Jersey), which has a lot of bridges, with the question of whether that network had an Eulerian path. I don't remember the answer. I also think it wouldn't be as much fun; New York has lots of traffic and is much larger than Kaliningrad.
Subscribe to:
Post Comments (Atom)
7 comments:
Re New York:
1. Do the Bronx and New Jersey count as the same landmass?
1a. If not, is the Tappan Zee Bridge part of the network?
2. Do tunnels count?
More re New York:
3. The question of an Eulerian path (once one defines the crossings) is not too tricky. However, if more than one Eulerian path exists, there is the more practical question of which Eulerian path minimizes the money that one must spend. (I think that, for all crossings which have tolls, tolls are charged in one direction only.)
4. The question of what constitutes a "crossing" of the (essentially Y-shaped) Triborough Bridge is an unusual one.
The time to cross the George Washington Bridge tends to infinity, anyway.
I'd imagine the Bronx and New Jersey would be considered different land masses, and the Tappen Zee would not count (since both sides are outside the city limits). Similarly, I'd imagine you'd have to consider Randall's Island as a separate landmass, and treat the Triborough Bridge as three bridges.
It also turns out that (vehicular, see below) tunnels don't matter, because they only come in pairs (Lincoln and Holland, Queens-Midtown and Brooklyn-Battery).
The question of whether or not to consider mass-transit or pedestrian crossings or only vehicular crossings is an interesting one, though. There are lots of tunnels and a couple bridges that only carry trains, and they affect Randall's Island in particular (the Ward's Island Bridge is pedestrian-only and there are two rail-only bridges).
Also, the minor islands would affect your result significantly. There are either one or three bridges to Roosevelt Island, depending on if you want to count the Queensboro Bridge as being two bridges with a break in the middle at Roosevelt Island or one bridge that connects Queens with Manhattan, and there is one bridge to Riker's Island.
So, an interesting problem, to be sure, but more in the definition than in the solving :)
slimandslam:
1. For this purpose, I would count them as two landmasses, as (a) it is very impractical to cross from one to the other without a water crossing, and (b) if you limit it to NYC and NJ, there is no way to get from the Bronx to NJ without leaving NYC.
1a. I wouldn't count it; It's not in NYC at all, connecting two towns in NY north of NYC.
2. That could lead to two different versions of the problem with/without tunnels.
3. Directionality of crossing opens up other cans of worms. Are any bridges in NYC one-way? Has anyone studied Eulerian Paths on graphs which have a mixture of unidirectional and bidirectional paths? Are there weighted graph traversal theories which handle graphs with differing weights based on the direction one takes an edge?
4. I looked at the Triborough Bridge, and decided to treat it as three bridges joining Manhattan, Long Island, and the Bronx with Wells Island. Since Wells Island isn't on the list of land masses, I eliminated the Triborough from consideration.
There is also the Wells Island bridge, which connects Manhattan to Wells Island. However, I don't believe there is a way to get from the Triborough Bridge to the Wells Island bridge without going through Manhattan, so that would open up another can of worms -- two bridges going to the same landmass you can't get between without leaving that landmass.
That made me really happy to see the photos that someone took of the bridges in Kalingrad -- it's exactly what I would want to do if I could ever make it over there!
Back in April I had the revelation (sparked by a student presentation) that I could see Kalningrad on Google Maps. I'm not sure if html will work in the comments, but in case it does try clicking here to see it.
Apparently Google maps changed its mind about how it would navigate between the points in Kaliningrad described in the link. The following reproduces the original route:
http://maps.google.com/maps?f=d&hl=en&geocode=8793289529618164813,54.706323,20.510901%3B8722180152440938070,54.708610,20.507790%3B14279515469394328461,54.708720,20.515130%3B1535730972432693657,54.706094,20.514653&saddr=%D0%9A%D0%B0%D0%BD%D1%82%D0%B0+%D1%83%D0%BB.+%4054.706323,+20.510901&daddr=%D0%9B%D0%B5%D0%BD%D0%B8%D0%BD%D1%81%D0%BA%D0%B8%D0%B9+%D0%BF%D1%80%D0%BE%D1%81%D0%BF.+%4054.708610,+20.507790+to:%D0%9C%D0%BE%D1%81%D0%BA%D0%BE%D0%B2%D1%81%D0%BA%D0%B8%D0%B9+%D0%BF%D1%80%D0%BE%D1%81%D0%BF.+%4054.708720,+20.515130+to:54.705954,20.51465&mra=dme&mrcr=2&mrsp=3&sz=15&dirflg=w&doflg=ptk&sll=54.705086,20.513277&sspn=0.015621,0.026608&ie=UTF8&ll=54.704863,20.511217&spn=0.015621,0.026608&z=15
Post a Comment