Take the 2-minute tour ×
Mathematica Stack Exchange is a question and answer site for users of Mathematica. It's 100% free, no registration required.

I have a question regarding a graph traversal problem. This is the graph I am working with:

Graph[{1 <-> 2, 1 <-> 3, 2 <-> 3, 2 <-> 4, 3 <-> 4}]

enter image description here

My Problem is following:

I want to find a cycle on this graph such that after completion of the cycle I will have traversed each edge of the graph exactly twice and will have ended at my starting point.

I saw that Mathematica 9 has a built-in function: FindEulerianCycle[g] which does just want I want except that each edge is traversed exactly once. So my idea was to "double" the edges i.e. add a new edge between 2 nodes:

Graph[{
  1 <-> 2, 1 <-> 2, 1 <-> 3, 1 <-> 3, 2 <-> 3, 2 <-> 3, 2 <-> 4, 2 <-> 4, 3 <-> 4, 3 <-> 4
  }]

But then I get the following error message:

Graph::supp: Mixed graphs and multigraphs are not supported.

Apparently Multigraphs are still not supported in Mathematica 8 & 9: Multigraphs in Mathematica 8

Is there a way to implement a solution to the above mentioned problem in Mathematica? (I am using Mathematica 9)

Note: The graph shown above is just a simple example. I need to solve the above mentioned problem on a much bigger undirected graph which has vertices of odd degree.

share|improve this question

3 Answers 3

up vote 4 down vote accepted

You could convert your graph to directed graph by doubling your edge and give directions (opposite each other):

g = Graph[{1 <-> 2, 1 <-> 3, 2 <-> 3, 2 <-> 4, 3 <-> 4}];
dg = DirectedGraph[g]

enter image description here

path = FindEulerianCycle[dg][[1]]

{1 [DirectedEdge] 2, 2 [DirectedEdge] 1, 1 [DirectedEdge] 3, 3 [DirectedEdge] 2, 2 [DirectedEdge] 3, 3 [DirectedEdge] 4, 4 [DirectedEdge] 2, 2 [DirectedEdge] 4, 4 [DirectedEdge] 3, 3 [DirectedEdge] 1}

once you found path you can convert edges back to undirected:

UndirectedEdge @@@ path

{1 <-> 2, 2 <-> 1, 1 <-> 3, 3 <-> 2, 2 <-> 3, 3 <-> 4, 4 <-> 2, 2 <-> 4, 4 <-> 3, 3 <-> 1}

Note: this will just work on new version of Mathematica (tested on wolframcloud): https://www.wolframcloud.com/objects/4b9a4eea-4577-4799-844b-85da34f7550f

share|improve this answer
    
I don't understand how using 2 oppositely directed edges like this is guaranteed to work. As you "use up" the edges whilst building a (potentially) Eulerian path, the directedness of the "unused" edges constrains the remaining possible routes for the path by MORE than if the edges are undirected. Is there something rather subtle going on in your proposed approach? Unfortunately, I can't think of a counterexample, which is why I am asking this question. –  Stephen Luttrell Jun 27 at 14:10
1  
@StephenLuttrell if a graph is directed and has equal in and out degree at each vertex, then graph is eulerian. So by replace edge with 2 oppositely directed edges, we guarantee satisfying this condition. –  halmir Jun 27 at 14:42
    
So that's why I couldn't think of a counterexample! It's now obvious to me how this property is true - i.e. an inductive proof where the graph is built up one vertex/edge-pair at a time. –  Stephen Luttrell Jun 27 at 15:14
    
I tested this on Mathematica 9. It also works there. –  user3780157 Jun 28 at 8:48

Mathematica 10 now supports multigraphs, so you can simply use FindEulerianCycle.

Here's an example run in Wolfram Cloud using a free account:

enter image description here

share|improve this answer
1  
This is better than the other answer because this allows the second traversal to occur in either direction. –  anorton Jun 26 at 20:10
    
@anorton The only problem is that at this moment Mathematica 10 is not released yet, so the only option to use this method is using the Programming Cloud. –  Szabolcs Jun 26 at 20:11
    
Oh. Well, that is a problem... now I see why the other answer is popular, too. –  anorton Jun 26 at 20:13

I think the easiest solution is to just solve for the single traversal and then just reverse it. You should cover each edge exactly once on your "trip back" and wind up where you originally started. Then you don't need to double any edges or anything (which I imagine would greatly increase the complexity as n gets bigger and bigger.

share|improve this answer
1  
1. How would you solve for the single traversal? 2. In some cases the double traversal is possible, but the single traversal is not. Example: {1 <-> 2, 1 <-> 3, 1 <-> 4}. –  Szabolcs Jun 26 at 22:16
    
OP has a solution for single traversal in the post itself, FindEulerianCycle. As for the double being possible where the single is not, point taken: but OP specifically stated that FindEulerianCycle, quote, "does just want I want except...". –  corsiKa Jun 26 at 22:18
    
FindEulerianCycle will only find cycles, which is not possible in many many cases (1 <-> 2). I thought that "by single traversal" you meant finding a path that taverses every edge once, but is not necessarily a cycle, and you're not realizing that even with lifting the restriction that we're looking for a cycle (FindEulerianCycle) it is not always possible to do this. –  Szabolcs Jun 26 at 22:20
    
I'm not concerned about the limitations of FindEulerianCycle because OP already stated that it is sufficient for his needs. If it's good enough for his needs, it's good enough for me to solve his problem. –  corsiKa Jun 26 at 22:26
    
It sounds like you misunderstood the OPs statement. He said that FindEulerianCycle would work if multigraphs were supported. Do you know what Eulerian cycle means? Did you understand why the graphs I mentioned are counterexamples that cannot be solved with your method? –  Szabolcs Jun 26 at 22:29

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.