0

I know that my question is more about graphs than programming but, I like the community here which is very active and you guys may have work with graphs.

So here Im wondering if the set of the Eulerian cycle of a non-oriented graph can contain more than one.

Thanks

Guy Coder
  • 24,501
  • 8
  • 71
  • 136
Indray
  • 19
  • 2

2 Answers2

1

The cycle is called Eulerian, iff it contains all edges, exactly one time each. That means that Eulerian cycles can only differ by edge's order (I propose to exclude edge's cyclical permutations as trivial option).

It is possible to find Eulerian cycle, using Fleury's algorithm: in short, move as you like (throwing out the edges you went on), but do not cross the bridge until the whole component is done. "The bridge" is the edge which is the only remaining way between different graph's components.

The proposed algorithm is quite old and well-known, so I won't prove its correctness.

Now, it should be quite obvious that there are graphs containing many different Eulerian cycles.

Matt
  • 13,674
  • 1
  • 18
  • 27
0

Yes, they often do. Have a look at this example, which contains multiple disjunct edge circles - you can build many different Eulerian circles from them:

Taken from German Wikipedia, created by Chin tin tin

Community
  • 1
  • 1
Bergi
  • 630,263
  • 148
  • 957
  • 1,375
  • Alright, but just to be sure : according to what I read an Eulerian cycle is an Eulerian chain with the same first and last node. And an Eulerian chain must contain all the edges right ? May you tell me more about this please ? – Indray Feb 28 '15 at 12:54
  • @Indray: Yes, that's how they are defined. – Bergi Feb 28 '15 at 13:15