3
$\begingroup$

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.

$\endgroup$
0

4 Answers 4

7
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$ Jun 27, 2014 at 14:10
  • 1
    $\begingroup$ @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. $\endgroup$
    – halmir
    Jun 27, 2014 at 14:42
  • $\begingroup$ 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. $\endgroup$ Jun 27, 2014 at 15:14
  • $\begingroup$ I tested this on Mathematica 9. It also works there. $\endgroup$ Jun 28, 2014 at 8:48
10
$\begingroup$

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

$\endgroup$
3
  • 1
    $\begingroup$ This is better than the other answer because this allows the second traversal to occur in either direction. $\endgroup$
    – apnorton
    Jun 26, 2014 at 20:10
  • $\begingroup$ @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. $\endgroup$
    – Szabolcs
    Jun 26, 2014 at 20:11
  • $\begingroup$ Oh. Well, that is a problem... now I see why the other answer is popular, too. $\endgroup$
    – apnorton
    Jun 26, 2014 at 20:13
0
$\begingroup$

just perform dfs (depth first search) on the graph. store vertices as they are explored and when returning from the vertex. like, a---b---c is a graph. on dfs, vertices will be stored as (a,b,c,b,a) . hence it is the desired path.

$\endgroup$
-1
$\begingroup$

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.

$\endgroup$
8
  • 1
    $\begingroup$ 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}. $\endgroup$
    – Szabolcs
    Jun 26, 2014 at 22:16
  • $\begingroup$ 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...". $\endgroup$
    – corsiKa
    Jun 26, 2014 at 22:18
  • $\begingroup$ 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. $\endgroup$
    – Szabolcs
    Jun 26, 2014 at 22:20
  • $\begingroup$ 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. $\endgroup$
    – corsiKa
    Jun 26, 2014 at 22:26
  • $\begingroup$ 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? $\endgroup$
    – Szabolcs
    Jun 26, 2014 at 22:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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