# The Bridges of Konigsberg and Instant Insanity

### 34 Responses

1. Mad Rocket Scientist says:

It’s been a while since I’ve had cause to use one as a data structure, but graphs are common in computer science specifically because they lend themselves well to searching & sorting algorithms.

Reply

Report

• veronica d in reply to Mad Rocket Scientist says:

Actually, almost anything in CompSci can be mapped over to graphs. For example, integer programming programs are typically presented in linear algebra form. However, if they fit certain (not uncommon) constraints, they can be represented as network flow problems (over a graph), which then allow for more efficient solutions. Doing such things is literally routine. In fact, I seldom dig too deeply into a problem before I try to turn it into a graph.

Reply

Report

• veronica d in reply to veronica d says:

Of course it cuts both ways. Google’s original Page Rank problem looks at first like a graph problem, but it is solved as an eigenvector problem. Cuz math is awesome!

Reply

Report

• Kimmi in reply to veronica d says:

Pathing too, and emergent behavior.

Reply

Report

• Mad Rocket Scientist in reply to veronica d says:

Which is kinda how I used them in my masters thesis, to navigate an unstructured mesh.

Reply

Report

2. Burt Likko says:

@michael-cain, I’m not sure this is the sort of post that gains a lot of comments, but I thought I’d let you know that I enjoyed reading it. You got me to exercise a part of my brain that doesn’t often get to come out and play.

Reply

Report

3. Richard Hershberger says:

It was possible to doctor a Rubik’s cube to make it unsolvable by carefully prying out a corner piece, rotating it, and putting it back in place.

Reply

Report

• Road Scholar in reply to Richard Hershberger says:

Similarly, IIRC, if you start with an empty Sudoku grid and just randomly fill in some spaces to make a plausible puzzle, i.e., no obvious repeats in any row, column, or block, there’s exactly fifty percent chance that it’s solvable.

I seem to remember the same sort of thing applying to a Rubik’s cube.

Reply

Report

• Mike Schilling in reply to Richard Hershberger says:

Rubik cubes have three kinds of parity:

If you exchange any two pieces, it becomes insolvable. If then you exchange any two pieces a second time, it becomes solvable again.

If you flip any edge piece it becomes insolvable. If then you flip any edge piece a second time, it becomes solvable again.

If you rotate any corner piece it becomes insolvable. To make it solvable again, you need to flip a corner piece in the opposite direction, or flip two corner pieces in the same direction.

So, if you take it completely apart and put it back together at random, there’s a 1/12 chance the result can be solved.

Reply

Report

4. Road Scholar says:

You’ve given me something to ponder that will drive me to distraction until I understand exactly why this works like this. Thanks a lot, Obama!

Reply

Report

• Glyph in reply to Road Scholar says:

Just don’t try to work out the proofs using your truck and bridges on your route. That’ll waste a lot of gas.

Reply

Report

• Jaybird in reply to Glyph says:

If elected Mayor of Konigsberg, I will make my number one priority the building of an eighth bridge!

Reply

Report

• Michael Cain in reply to Glyph says:

IIRC, Königsberg’s bridges didn’t all survive WWII bombings, they only have five now, and an Euler walk is possible. Bummer for the students: “Dammit, Franz, now that you’ve solved the puzzle we’ll have to find another excuse to wander around drinking!”

Reply

Report

• If you get really stuck, you can always post questions in a comment, or I think if you follow my gravatar there’s an e-mail address that gets checked regularly.

Reply

Report

5. Kazzy says:

I just have to say that using the term “graph” to describe what you describe above when it has a much more commonly known/understood definition within the discipline of math is… confusing.

I recognize you are using the terms properly. It’s just strange that the terms exist as they do.

Reply

Report

6. Mike Schilling says:

Euler was one of the titans of mathematics. (Yes, that is a pun.)

Reply

Report

7. zic says:

In my design work, I do a lot of graphing. Maybe it’s the stitch-twistings for a complicated Aran sweater, with all it’s ropes and honeycombs, or charting a lace pattern or colors patterns for a Fair Isle sweater or teddy bear design on a kid’s sweater.

But that’s basically all flat (or a cylinder), and knitting is 3-d (or else your socks wouldn’t have heels, socks didn’t used to have heels, in fact, the heel was a giant innovation in the craft). I often make sculptures, things knit freeform to resemble a horse, a flower, a leaf, etc. It’s easy to do, I comprehend how to get the shapes I want, and I have strong three-dimensional perception, for a girl in particular. (Seriously, army tried hard to recruit me, they told me all about it at length on multiple occasions).

The problem is, it’s difficult to 2-D charts for 3-D objects.

Until this came along (and chart hounds, please take a look.)
http://stitch-maps.com/

You can’t imagine how this very-recent innovation twitterpated the knitting world.

Reply

Report

• Michael Cain in reply to zic says:

Somewhat relatedly, one of the graph theory problems that goes back a long time is deciding whether a particular (usually large) graph can be drawn on a plane without any of the edges crossing. Eg, the very first figure in the post is drawn with two edges crossing, but could be redrawn so that they don’t cross. This problem, and algorithms for finding how to draw the graph, got a lot of attention when the wiring for integrated circuits and printed circuit boards began to get seriously complicated.

Reply

Report

• Road Scholar in reply to Michael Cain says:

There’s a game app based on that idea you might enjoy called “Flow [Free]”. My ten-year old loves it. Who woulda guessed she was a natural at graph theory? 😉

Reply

Report

• zic in reply to Michael Cain says:

I believe it. And I’m not surprised that it’s its own science, either.

What intrigues me about the charting system I linked to was who uses it: often people who have little math background, and little more then rudimentary design skills; but this charting system is so representative of the work they’re producing that it’s almost intuitively understandable; the biggest challenge is coming up with a marking system to keep your place as you work through it. That’s a pretty impressive step forward in charts and graphs for everyday use of an ancient craft.

The system it replaces (still the norm) uses a straight grid with grayed-out areas for places where there are ‘no stitches,’ allowing for 3-D patterns to grow rather like a flattened-out orange peel or map of the globe, but also very confusing for people who don’t get that flattening produces gaps in the 2-D representation.

Reply

Report

8. James K says:

Interesting post @michael-cain

Graph Theory isn’t something I do much (there’s not much call for it in economics), but it did come in handy for one of the puzzles in Dragon Age: Inquisition.

Reply

Report