Bioinformatics Algorithms/

...

/

Constructing Eulerian Cycles and Paths from Euler’s Theorem

Constructing Eulerian Cycles and Paths from Euler’s Theorem

Let’s construct Eulerian cycles and paths by using Euler’s theorem.

We'll cover the following...

Algorithm for finding an Eulerian cycle

The proof of Euler’s Theorem offers an example of what mathematicians call a constructive proof, which not only proves the desired result but also provides us with a method for constructing the object we need. In short, we track Leo’s movements until he inevitably produces an Eulerian cycle in a balanced and strongly connected graph Graph, as summarized in the following pseudocode.

We’ll also take a look at the following function that will generate Eulerian Cycles.

EulerianCycle(Graph)
    form a cycle Cycle by randomly walking in Graph (don’t visit the same edge twice!) 
    while there are unexplored edges in Graph
        select a node newStart in Cycle with still unexplored edges
        form Cycle’ by traversing Cycle (starting at newStart) and randomly walking 
        Cycle ← Cycle’
    return Cycle
Generating Eulerian cycles

We first have to form a cycle Cycle by visiting random edges in the graph while avoiding the edges already visited (line 2). Next, we have a loop that runs until there are no unexplored edges left (line 3). Here’s what the loop does:

  • Select newStart node in Cycle that still has unexplored edges.
  • Create a new cycle Cycle' by traversing through Cycle.
...