The Seven Bridges of Königsberg

May 31, 2013

Our exercise today studies a famous problem solved by the great Swiss mathematician Leonhard Euler in 1735, which marked the beginning of what is now the “graph theory” branch of mathematics. Euler proved that it was impossible to cross all seven bridges once without retracing your path. He proved that a complete circuit, returning to the starting point, is possible only if all vertices connect to an even number of neighbors, and a complete path that doesn’t return to the starting point is possible if exactly two of the vertices have an odd number of neighbors, the rest being even, in which case the two odd-count vertices are the starting and ending points of the path.

The following algorithm to determine a eulerian path in a graph, if it exists, is ancient; I would be happy if anybody can provide a pointer to the source of the algorithm:

1) If a complete circuit is possible, choose any vertex at random as the current vertex. If a complete path but not a circuit is possible, choose either of the two odd-degree vertices at random. Otherwise, quit.

2a) If the current vertex has neighbors, add it to the stack, choose any of its neighbors as the new current vertex, and remove the edge between the two vertices.

2b) If the current vertex has no neighbors, add it to the path, remove the last vertex from the stack and make it the current vertex.

3) Repeat step 2 until the current vertex has no neighbors and the stack is empty.

4) Add the current vertex to the path and quit.

Your task is to write programs that determine if a graph is an eulerian circuit or eulerian path and, if it is, determine the path. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

About these ads

Pages: 1 2

2 Responses to “The Seven Bridges of Königsberg”

  1. […] today’s Programming Praxis exercise, our goal is to write a function that determines whether a given graph […]

  2. My Haskell solution (see http://bonsaicode.wordpress.com/2013/05/31/programming-praxis-the-seven-bridges-of-konigsberg/ for a version with comments):

    import Data.List
    import qualified Data.Map as M
    
    check :: Ord a => M.Map a [a] -> Maybe (String, [a])
    check graph | notElem (length . filter (odd . length) $ M.elems graph) [0,2] = Nothing
                | head path == last path = Just ("Circuit", path)
                | otherwise              = Just ("Path", path)
        where path  = walk [] graph start
              start = maybe (last $ M.keys graph) id $
                      find (odd . length . (graph M.!)) $ M.keys graph
    
    walk :: Ord a => [(a, [a])] -> M.Map a [a] -> a -> [a]
    walk stack g v = case (g M.! v, stack) of
        (n:_,_)        -> walk ((v, g' M.! v):stack) g' n where
                          g' = M.adjust (delete n) v $ M.adjust (delete v) n g
        ([] ,(s,_):ss) -> v : walk ss g s
        ([] ,[])       -> [v]
    

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 630 other followers

%d bloggers like this: