The Bridges of Konigsberg and Instant Insanity

Related Post Roulette

34 Responses

  1. Avatar 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.Report

    • Avatar 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.Report

  2. Avatar 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.Report

  3. Avatar 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.Report

    • Avatar 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.Report

    • Avatar 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.Report

  4. Avatar 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!Report

  5. Avatar 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.Report

  6. Avatar Mike Schilling says:

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

  7. Avatar 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.)

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

    • Avatar 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.Report

      • Avatar 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? 😉Report

      • Avatar 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.Report

  8. Avatar 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.Report