Notices
Results 1 to 13 of 13

Thread: Seven Bridges of Königsberg

  1. #1 Seven Bridges of K√∂nigsberg 
    Forum Sophomore numb3rs's Avatar
    Join Date
    Mar 2008
    Posts
    166


    there has to be a way to cross all seven of these briges just once and only once its driveing me mad


    Reply With Quote  
     

  2.  
     

  3. #2  
    Moderator Moderator AlexP's Avatar
    Join Date
    Jul 2006
    Location
    NY
    Posts
    1,838
    Sorry to burst your bubble, but Leonhard Euler proved that it can't be done in 1736. And I wouldn't question Euler if I were you, he was a very smart guy. There's a Wikipedia article on the subject if you'd like to take a look at it.


    "There is a kind of lazy pleasure in useless and out-of-the-way erudition." -Jorge Luis Borges
    Reply With Quote  
     

  4. #3  
    Forum Professor serpicojr's Avatar
    Join Date
    Jul 2007
    Location
    JRZ
    Posts
    1,069
    Notice that all four landmasses have an odd number of bridges leading to them. Now suppose you made a full circuit of all the bridges without repeating. Then you started in some landmass, and you ended in some landmass. So the two landmasses you neither started nor ended on must have been visited by you an even number of times--for each time you visited one of them, you also left it. So they must be attached to an even number of bridges, which is not the case.
    Reply With Quote  
     

  5. #4  
    Forum Sophomore numb3rs's Avatar
    Join Date
    Mar 2008
    Posts
    166
    i found a way to do it!
    you go through some of the briges half way and walk back thats 1 time and you can do it!
    Reply With Quote  
     

  6. #5  
    Forum Bachelors Degree Demen Tolden's Avatar
    Join Date
    Sep 2007
    Location
    St. Paul, Minnesota, USA
    Posts
    475
    i found a way to do it!
    you go through some of the briges half way and walk back thats 1 time and you can do it!
    Why not swim across that blue stuff a couple times just for good measure?
    The most important thing I have learned about the internet is that it needs lot more kindness and patience.
    Reply With Quote  
     

  7. #6  
    Forum Sophomore numb3rs's Avatar
    Join Date
    Mar 2008
    Posts
    166
    but thats cheating
    my grammer is not to be made fun of
    Reply With Quote  
     

  8. #7  
    Forum Professor sunshinewarrior's Avatar
    Join Date
    Sep 2007
    Location
    London
    Posts
    1,526
    It's actually quite easy - the surface of the earth is, literally, curved space. Simply walk around the earth from one of the bridges (chosen carefully) to come back to the opposite side of Konigsberg, and Bob's your uncle.
    Reply With Quote  
     

  9. #8  
    Forum Masters Degree bit4bit's Avatar
    Join Date
    Jul 2007
    Posts
    621
    I was reading about this problem recently, looking into topology. Euler proved that to take a route using each path only once, called a Euler path, you would have to have exactly 2 or exactly 0 odd nodes, otherwise it cant be done. A node would be a landmass, and if it has an even number of bridges connecting it, it is even, but if it has an odd number it is odd. This is all about considering how the landmasses (nodes) are connected by the bridges, and not thinking about any physical geometry of the situiation.
    Reply With Quote  
     

  10. #9  
    Forum Professor sunshinewarrior's Avatar
    Join Date
    Sep 2007
    Location
    London
    Posts
    1,526
    Quote Originally Posted by bit4bit
    I was reading about this problem recently, looking into topology. Euler proved that to take a route using each path only once, called a Euler path, you would have to have exactly 2 or exactly 0 odd nodes, otherwise it cant be done. A node would be a landmass, and if it has an even number of bridges connecting it, it is even, but if it has an odd number it is odd. This is all about considering how the landmasses (nodes) are connected by the bridges, and not thinking about any physical geometry of the situiation.
    Absolutely true - unless you consider that the nodes have different properties (and Euler's proofs different considerations) depending on the shape of the surface. For instance, I'm guessing that Euler's proof is concerned solely with plane surfaces (or surfaces with a particular topological characteristic - order 0?) but does not hold for spheres, mobius strips, klein bottles or toroids.
    Reply With Quote  
     

  11. #10  
    Forum Professor serpicojr's Avatar
    Join Date
    Jul 2007
    Location
    JRZ
    Posts
    1,069
    I don't think Euler's proof depends on topology (and I'm pretty sure the proof I posted is essentially Euler's proof). Actually, let me restate this: it doesn't depend upon the topology of the surface upon which the problem exists. The key assumption is that there is no way to get between two landmasses without crossing a bridge (or without getting wet), and so the problem can be abstracted to a question about graphs (vertices connected by edges). Sure, the graph has topological properties, and I'm sure you can use these to prove the result, but it's not necessary, as my proof shows. And it doesn't matter what sort of surface you put this graph on, you still can't do it.

    The only way for there to be a solution to the problem is, as you suggest, consider the idea that some of the landmasses may be connected if you walk far enough. And this isn't in the spirit of the original problem--people wanted to be able to walk all of the bridges in a single day.
    Reply With Quote  
     

  12. #11  
    Forum Masters Degree bit4bit's Avatar
    Join Date
    Jul 2007
    Posts
    621
    I think the proof can be stated simply, as you said (And I repeated), but it seems to be given as an example of topology in alot of pages i have read. As far as explaing why that is, I don't know enough topology, to say.
    Reply With Quote  
     

  13. #12  
    Forum Professor serpicojr's Avatar
    Join Date
    Jul 2007
    Location
    JRZ
    Posts
    1,069
    This is a topological question in the sense that it doesn't matter where the nodes are in relation to each other, which order the bridges are in, etc. We can pull and push and stretch and bend things around without changing the nature of the problem. Like you said, the actual geometry of the picture doesn't matter. Indeed, everything rests upon the fact that, when you're on a bridge, the world locally looks like a line, whereas when you're at a node, the world looks like an arbitrary set of rays--and these are topological facts. These facts basically characterize what the possible paths through the space are (up to some sense of equivalence).

    I suppose what I was saying, then, is that these basic topological properties of graphs are basically assumed/formalized when you're doing graph theory.
    Reply With Quote  
     

  14. #13  
    Forum Professor sunshinewarrior's Avatar
    Join Date
    Sep 2007
    Location
    London
    Posts
    1,526
    Quote Originally Posted by serpicojr

    The only way for there to be a solution to the problem is, as you suggest, consider the idea that some of the landmasses may be connected if you walk far enough. And this isn't in the spirit of the original problem--people wanted to be able to walk all of the bridges in a single day.
    Fair enough. And your proof was elegant. Ta. :-D
    Reply With Quote  
     

Bookmarks
Bookmarks
Posting Permissions
  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •