Wednesday, April 13, 2016

K is for . . .

Source: Scottish Bridge by Judit Bermudez Morte


Königsberg Bridge. The town of Königsberg (now Kaliningrad) is in Russia. Königsberg had seven bridges joining the two sides of the river and also an island and a peninsula. (Source: Gates, Les Bill. "Activity: The Seven Bridges of Königsberg" Math Is Fun. Ed. Rod Pierce. 24 Jan 2014. 12 Apr 2016 http://www.mathsisfun.com/activity/seven-bridges-konigsberg.html) This is also the source for the following three images.)



Mathematician Leonhard Euler was asked if it was possible to walk through Königsberg, visit each part, and cross each bridge only once. (You can visit city "parts" more than once.)

In order to made the problem easier, we use Graph Theory. First we simplify the picture, labeling each part of town with a capital letter (A, B, C, and D) and each bridge with a lower case letter (p, q, r, s, t, u, v):


Otay! Now grab a stylus and get walking. Let's try the path A-p-C-r-B-s-C-q-A-u-D-v-B oh crap, we would have to cross bridge r or s or v to get to bridge t. Try a few more routes and you'll get the feeling such a walk is not possible. That is correct. Why not?

Let's change the picture a bit more, representing each part of the city with a dot (called a vertex in graph theory) and each bridge with a line (called an edge in graph theory). The resulting picture is called a graph. A path that passes through each edge (bridge) exactly once is an Euler path.


It looks like a pair of dropped ice-cream cones, doesn't it? This problem would be much easier if the bridges labeled q, s, and t disappeared. Then we could merrily go in a simple circle A-p-C-r-B-v-D-u- and be back at A. Done and done. Or add another bridge, say bridge w between B and C. Then our first attempt could be completed as: A-p-C-r-B-s-C-q-A-u-D-v-B-w-C-t.

Now let me throw another graph theory definition at you: the degree of a vertex (dot) is the number of edges next to that vertex. Since A is next to bridges p, q, and u, its degree is 3 or d(A)=3. Similarly, d(B)=3, d(C)=5, and d(D)=3. 

If we took away bridges p, q, and t, the degrees would be d(A)=2, d(B)=2, d(C)=4, and d(D)=2.

So does the Euler path only exist if the degrees are all even? Not quite.

If we added our bridge w between B and C, the degrees would be d(A)=3, d(B)=4, d(C)=6, and d(D)=3, and our Euler path (A-p-C-r-B-s-C-q-A-u-D-v-B-w-C-t) does exist.

So what's up? The solution is this: A graph has an Euler path if there are no vertices with an odd degree or two vertices with an odd degree.

Ta-DAH! Extra gold star if you followed this blog to the end. Are you a math hater, tolerator, or lover? 





14 comments:

  1. I think I may need another cup of coffee before I properly comprehend that.
    I mostly dislike math. Don't ask me how it ended up in my novel...

    ReplyDelete
  2. Wow! Yeah, my head hurts. But I did read the post until the end. I am actually interested enough to go back and now try to understand it.

    ReplyDelete
  3. In theory I am a math lover but in practice I get lost a lot but your analysis is very impressive.

    Meet My Imaginary Friends
    #AtoZchallenge http://www.kathleenvalentineblog.com/

    ReplyDelete
  4. Math lover here! And I have a goal of seeing old bridges in Europe and take a few selfies on them.

    ReplyDelete
  5. Oh dear, my brain is fried, but due to minor surgery today, right now nothing is making sense. But still, I'm not a math person, but walker, oh yeah. I'll just take the most scenic route and if I cross more than once I won't mind! LOL

    ReplyDelete
  6. If "followed" means I read it to the end, then I followed it to the end. But if it means I UNDERSTOOD it till the end ... then I guess my ruse is up. I just heard a couple synapses explode. Ouch.

    ReplyDelete
  7. I can see your mathematician side :) I think I get it. I was really good at math in school to a point that I got bored with it. I did come back around in college with an elementary teaching math class which was a lot of fun!

    ReplyDelete
  8. I always liked maths, but my brain is currently going 'duh, what?' :) I think I need to come back when I have my brain in gear, or maybe that is just a faint hope ;)
    Tasha
    Tasha's Thinkings | Wittegen Press | FB3X (AC)

    ReplyDelete

I will do everything in my power to visit commenter's blogs unless I've been abducted by aliens or my children get sick. (If my children get abducted by aliens, I will be very busy, of course, catching up on my sleep.)