Re: Finding Euler paths..

From: Ian Woods (newspub2_at_wuggyNOCAPS.org)
Date: 01/28/04 

Date: Wed, 28 Jan 2004 14:21:01 +0000 (UTC)

bhaskaraaditya@msn.com (Bhaskara Aditya) wrote in
news:4aae922e.0401280327.1be8cd4f@posting.google.com:

> Hi everyone,
> I have been trying to solve a problem where the aim is to find a
> Euler path in a graph taking input as the edges. The basic idea is to
> keep removing cycles from the graph and finding paths in the remaining
> graph.. but I am not able to implement it. Could anyone tell how to go
> about implementing/any easier way.
>
> Thanks in advance for any help,
> Bhaskara Aditya

For completeness, I'll describe the algorithm and then apply it to a
graph as an example, and show how the merging is done. If you're finding
Euler cycles, pay attention to the things in square brackets!

First thing, check that there can exist a euler path in the graph. For
that, there must be exactly 2 vertices with an odd number of edges and
the graph must be connected. [For a Euler cycle, all vertices must have
even degree.]

Next, find any old path that goes between the two vertices with odd
degree. A depth first search will do nicely for this, starting at one of
the vertices with odd degree and 'watching for' the other, where we stop
and accept the path. [For a Euler cycle, find any old cycle to start
with. Again, a DFS can do this easilly, stopping when we reach the start
vertex again].

Remove the edges for the path [cycle] from the graph, and record the path
[cycle].

Find further cycles in the graph, removing the edges used and recording
the cycle.

Merge the path with the found cycles [Merge the cycles together, in the
case of a Euler cycle.]

Now, for an example:

       1
      / \
     / \
    2-----3
    |\ /|
    | \ / |
    | X |
    | / \ |
    |/ \|
    5-----6
    | |
    7 8

Well, we know there's a Euler path in this graph since it meets the
conditions. So, we hunt any old path from 8 to 9, and remove the edges.

       1
      / \
     / \
    2-----3
    |\ /|
    | \ / |
    | X |
    | / \ |
    |/ \|
    5 6
           
    7 8

Path : 7 -> 5 -> 6 -> 8

Find any old cycle, remove the edges it uses and record it.

       1
      / \
     / \
    2-----3
    |\ /|
    | \ / |
    | X |
    | / \ |
    |/ \|
    5 6
           
    7 8

Path : 7 -> 5 -> 6 -> 8
Cycle: 1 -> 2 -> 3 -> 1

       1
         
          
    2 3
    |\ /|
    | \ / |
    | X |
    | / \ |
    |/ \|
    5 6
           
    7 8

And there's only one possible cycle left... so we get the following paths
and cycles:

Path : 7 -> 5 -> 6 -> 8
Cycle: 1 -> 2 -> 3 -> 1
Cycle: 6 -> 3 -> 5 -> 2 -> 6

So now to the merging! Now, it's easy to see how we can combine the
second cycle with our starting path by 'inserting' the cycle at vertex 6
to get the path:

7 -> 5 -> 6 -> 3 -> 5 -> 2 -> 6 -> 8

But, it's less clear how we can merge the first cycle we found into that
path. The 'trick' is that all of the following are the same cycle:

1 -> 2 -> 3 -> 1
2 -> 3 -> 1 -> 2
3 -> 1 -> 2 -> 3

Either the second or third form can be inserted into our original path
easilly.

Algorithmically, the merging operation is far simpler than it looks. We
can insert any cycle into any path [or other cycle] if they share any
vertex and get a longer path [or cycle].

Path : 7 -> 5 -> 6 -> 8
Cycle: 1 -> 2 -> 3 -> 1
Cycle: 6 -> 3 -> 5 -> 2 -> 6

So, our original path shares no vertices with the first cycle, so we
can't insert it into our path yet. The second cycle shares vertices 5 and
6 so we can insert it into our original path to get things like:

7 -> 5 -> 2 -> 6 -> 3 -> 5 -> 6 -> 8 (insert using vertex 5)
7 -> 5 -> 6 -> 3 -> 5 -> 2 -> 6 -> 8 (insert using vertex 6)
7 -> 5 -> 3 -> 6 -> 2 -> 5 -> 6 -> 8 (insert using vertex 5, but going
the other way around the cycle!)

Our new longer path shares vertices 2 and 3 with the first cycle we
found. Again, we can insert the cycle in a few different ways.

As long as the graph is connected you will always be able to insert one
cycle at each stage into your Euler path [or cycle]. If the graph isn't
connected, there isn't a Euler path [or cycle], and you should detect it
at the beginning when you check the graph.

Hope this monstrous post helps!

Ian Woods 

-- 
"I'm a paranoid schizophrenic sado-masochist.
My other half's out to get me and I can't wait."
(c) Richard Heathfield, circa 1979

Relevant Pages

  • counting cycles
    ... :> its meaning is perfectly clear and non-controversial. ... If you try to graph it, ... Except that this cycle IS infinite. ... It's hard to know what you even COULD mean by an infinite cycle. ...
    (sci.logic)
  • Re: searching an example for the road coloring conjecture, degree 2
    ... >>connected directed graph with outdegree 2 admits an edge coloring such ... >>the smallest coprime cycle set has at least 3 elements. ...
    (sci.math.research)
  • Re: Shortest path algorithm in digraph with multiple goals?
    ... > lot of red edges (thus your solution will produce a huge graph). ... graph traversal algorithms. ... arcs" can occur in any cycle. ... which there have been 'k' previous traversals of the "counted" arcs. ...
    (comp.theory)
  • Re: Shortest path algorithm in digraph with multiple goals?
    ... > lot of red edges (thus your solution will produce a huge graph). ... graph traversal algorithms. ... arcs" can occur in any cycle. ... which there have been 'k' previous traversals of the "counted" arcs. ...
    (comp.programming)
  • Re: Traversable graphs
    ... How would one show that a connected graph with all vertices of even ... degree has an Eulerian circuit? ... Connect the two odd gree vertices with an edge. ... the result is an Euler path in G. ...
    (sci.math)