Seven Bridges of Königsberg | Hacker News Reader

Seven Bridges of Königsberg

en.wikipedia.org

92 pointsEndXA30 comments

The bridges today in modern Kalningrad.

https://www.google.com/maps/place/Knaypkhof,+Ulitsa+Kanta,+K...

It appears that the geometry has changed since Euler's time, or the diagram is incorrect. It appears that is the larger ( Lomse/ Oktyabrsky ) island that has the 4 bridges from the mainland rather than the smaller one (Kneiphof). Ironically; the topology appears preserved, so it doesn't actually matter, which underscores the point of Euler's achievement.

The cathedral on the island is beautiful and contains Immanuel Kant's tomb. It was bombed pretty severely in WW2, before that there were a bunch of buildings on the island:

> After the war, the cathedral remained a burnt-out shell and Kneiphof was made into a park with no other buildings. Before the war, Kneiphof had many buildings. One of the buildings was the first Albertina University building, where Immanuel Kant taught, which was situated next to the east side of the cathedral.

https://en.wikipedia.org/wiki/K%C3%B6nigsberg_Cathedral

Picture of it prior to WW2 (featuring more bridges?): https://upload.wikimedia.org/wikipedia/commons/3/38/Modell_D...

The cathedral got lucky as its skeleton, the walls, whats left after WWII fighting and bombing, were allowed to survive through the Soviet times. During 198x were was a flea/farmers market inside and behind it.

The Castle didn't get that luck - https://en.wikipedia.org/wiki/K%C3%B6nigsberg_Castle. It got bulldozed, and the boondoggle of Soviet glory - the "skyscrapper" (21 story in Kaliningrad region in 198x was almost mindblowing, add to that that it is on the top of the Castle hill, so it looms large over the city) - is still unfinished and

(https://en.wikipedia.org/wiki/K%C3%B6nigsberg_Castle#Current... ) "Continuation of development was stopped in the 1980s as the massive building gradually sank into the structurally unsound soil stemming from the collapse of tunnels in the old castle's subterranean levels. Many people call this the "Revenge of the Prussians" or "The Monster"."

These underground tunnels (Kenigsberg and Prussia as whole has a lot of them) were back then and i'd guess even more today the scene of active exploration, in particular for hidden Nazi stolen treasures (e.g. "Amber room"), weapons/munitions/etc. and just out of sheer curiosity ( after all it is centuries of history starting from Teutonic Order). So you sometimes would find yourself facing a problem of "N tunnels in three dimensions" with some of them flooded/leading into unknown/etc.

My grandfather gave me a puzzle when I was 8 or 9 years old where the goal was to trace a path through each of the "walls" in the diagram below without the path crossing itself:

  ---------------------
  |        |          |
  ---------------------
  |    |        |     |
  ---------------------

I played with it off and on for years and suspected that it was impossible. I realized that it is in fact impossible when I took discrete mathematics in college and we covered the Seven Bridges.

I've passed this on to my kids but only let them play with it for hours until revealing that it's not possible and getting into the theory of it.

I don't think my grandfather knows this is impossible, and I haven't yet remembered to tell him.

Do it before it's too late. I used to have fun discussions with my grandparents about so many things. Then one day, well, they pass.

In fact, this five room puzzle is mentioned in the Königsberg article and also has an article of its own:

https://en.wikipedia.org/wiki/Five_room_puzzle

Your grandfather would likely enjoy discussing it with you!

Wow thank you! So I just learned the proper name of this "puzzle", which my father also showed me a long time ago (and for which I used to fill pages and pages of trials even though I knew that it had no solution), and which I tried to render as an "applet toy", a couple of years ago on my blog (see my other comment below).

It's interesting that there exists a solution (shown in the Wikipedia article), if you build the rooms on a torus. That would be the equivalent of digging a tunnel between two rooms.

The discussion of the "Variations" section is interesting. Apparently the person who inserted it (and had it removed several times) won't give a citation but also won't come out and say that they made the examples up themselves. Nobody ever calls out the useless introduction of German terms in the examples, and more importantly that (a) "Ritcher" is not a German word, and (b) even if it were a misspelling of some German word, it would not mean "church".

The closest German word is 'richter', which means judge. Church would be kirche. That is indeed a strange passage.

Why is the tangential, unsourced stuff always longer than the actual article?

http://enwp.org/Wikigroaning

Having knowledge of the material and writing it down is considered a negative when it comes to creating Wikipedia content.

The way the section was phrased (it's removed now) it appeared to refer to some external source. The sentence "It is understood that the problems to follow should be taken in order, and begin with a statement of the original problem:" would make no sense otherwise. But if there is such an external source, it should be cited. This is the main problem. It's not about Wikipedia being a boring stickler for rules.

I was fascinated by a "puzzle version" of this problem as a child, and a couple of years ago I wrote some little Processing applets to explore the idea of "gamifying" it:

https://cjauvin.blogspot.com/2012/02/implicit-bridges.html

https://cjauvin.blogspot.com/2012/02/eulerian-hoax.html

It's interesting that it's apparently the problem that laid the foundation for modern graph theory, but the problem can't actually be specified as a graph under its usual modern definition... can it? At least not without some shenanigans that would make it more complicated than "node = landmass, edge = bridge", as it's depicted in the standard diagram shown on Wikipedia.

A graph is usually defined as a set of nodes and a set of edges, where an edge is a pair of nodes (an ordered pair if it's a directed graph). The "set" of edges (bridges) of the "graph" in this case contains duplicates -- there are two edges with the same pair of vertices, two bridges crossing between the same pairs of landmasses. And the two pairs of duplicated bridges are essential to the problem setup. So AFAICT it can't be fully specified as a set of edges; it would have to be a multiset.

(I've seen this problem before but only just noticed this when reading Wikipedia now -- let me know if I'm missing something.)

A "graph" can sometimes implicitly mean a "Simple Graph" which has neither loops nor multiple edges between pairs of vertices, but in some contexts can mean "Multi-Graph", which does allow multiple edges and loops. So the usual conversion of the bridges problem to a network gives us a "Multi-Graph" ... the distinction is often left to be inferred, because it's usually obvious (to the skilled practitioner).

One way around this to end up with a simple graph is to include a vertex in the middle of each bridge. Then each edge has one end in the landmass and the other end in the middle of the bridge. That equivalence/conversion shows that the distinction, in this case, is effectively unimportant.

Yes, the image shown is a multigraph: https://en.wikipedia.org/wiki/Multigraph

Some friends and I took a holiday to NYC a few years ago, calling it "Project Königsberg" as we attempted to travel all public transport entry and exits to Manhattan without duplication, over the course of 3 days. I was glad not to be involved in its planning, but very happy to participate!

I loved the 2015 SIGBOVIK paper applying this idea to Pittsburgh bridges. Page 21 of https://archive.org/details/SIGBOVIK2015/mode/2up

William Hamilton has an interesting variation of Euler's Seven Bridges puzzle [0] which asks whether there is a path visiting every vertex of a polyhedron exactly once. Strangely, while the complexity of detecting Eulerian paths is linear in the number of edges [1], the complexity of detecting Hamiltonian paths is NP-complete [2]!

Hamilton (who was also fond of crossing bridges [3]) developed some interesting algebraic structures to study the polyhedron problem [4]. I recently became interested in Eulerian and Hamiltonian paths after taking a class in Graph Representation Learning [5]. In it, I learned there are many interesting connections between algebra and graph theory [6] and started writing a library called Kaliningraph to study some of those connections [7].

[0]: http://eulerarchive.maa.org/docs/originals/E053.pdf

[1]: https://en.wikipedia.org/wiki/Eulerian_path#Hierholzer's_alg...

[2]: https://en.wikipedia.org/wiki/Hamiltonian_path

[3]: https://en.wikipedia.org/wiki/Broom_Bridge

[4]: http://www.kurims.kyoto-u.ac.jp/EMIS/classics/Hamilton/PRIAI...

[5]: https://cs.mcgill.ca/~wlh/comp766/

[6]: https://www.cs.yale.edu/homes/spielman/sagt/sagt.pdf

[7]: https://github.com/breandan/kaliningraph

Soviet solution: bomb two of the bridges, therefore allowing an Eulerian path.

You mean an Alexandrian solution (to a Gordian knot?)

I think the GP was intended to be funny. (And, judging by the downvotes, HN still has zero tolerance for humor.)

Well, the HN/engineer solution would be to propose the building of a new bridge.

Then we could have a big discussion about funding strategies, metallurgical esoterica, cutting edge topological algorithms for determining best place to add a vertex in the graph, and/or history of Roman land jurisdiction. And we’d all learn something.

And maintain the old one for backward compatibility.

The problem states seven bridges, not seven or more. Clearly, the engineering would be a tunnel.

(the beaver solution would be a dam. "List of mathematical problems solvable by beavers")

Wouldn't you only need to bomb one bridge? Bombing one bridge reduces the degree of two vertices.

i was extremely lucky and had a great math teacher who pulled this one on us in 10th grade.

Good times.

Who cares about bridges when you can swim ?

Reply on news.ycombinator.com