2
$\begingroup$

How to generate random graphs with eulerian Paths? Its well known that there is a eulerian path if the number of nodes with odd degree is exactly 2 or zero. I'm interested in an algorithm to make uniformly distributed random graphs with such paths. Until know I've developed this simple algorithm: Given the number of nodes in the desired graph:

  1. Create a chain, by definition it is a eulerian path. With exactly 2 odd degree nodes.
  2. Take one of the odd nodes and make an edge with one of the even nodes (Both choose randomly). If multiple-edges between a pair of nodes is not allowed make an edge iff previously there is not an edge.
  3. Repeat step 2 until there is a maximum number of edges or an edge cannot be made.

This algorithms works for eulerian paths, but I think is highly biased and the graphs that it generates are just a sub set of all the eulerian paths that can be made (If not, how can be proved the contrary?).

In the other hand the algorithm above doesn't generate any eulerian tour. Is there a better approach to solve this task?

$\endgroup$
  • $\begingroup$ Thank you for the improvement. Can you clarify what you mean by a uniformly distributed random graph? You might want to take a look at en.wikipedia.org/wiki/Random_graph and en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93R%C3%A9nyi_model and see if any of those fit what you are looking for, and if so, edit the question to use that to make more precise what you mean by "uniformly distributed". $\endgroup$ – D.W. Aug 20 '15 at 7:13
  • $\begingroup$ @D.W. "uniformly distributed" usually means that you pick the number of vertices and you get back a graph that's sampled u.a.r. from the set of relevant (in this case, Eulerian) graphs on that number of vertices. ("Usually" in the sense that I've never seen it mean anything else in the context of random graphs.) $\endgroup$ – David Richerby Aug 20 '15 at 7:27
  • $\begingroup$ @DavidRicherby, got it, that makes sense. (Presumably this means "not taking into account graph isomorphism", so for a graph on $n$ vertices, if we disregard the Eulerian constraint, it's uniformly at random from a set of $2^{C(n,2)}$ possible graphs?) Thank you for the explanation. $\endgroup$ – D.W. Aug 20 '15 at 7:34
  • 2
    $\begingroup$ @D.W. Yes, ignoring isomorphism. So the distribution is the one you get from taking all edge sets over $\{1, \dots, n\}$, deleting the ones that aren't Eulerian and sampling u.a.r. from what remains. $\endgroup$ – David Richerby Aug 20 '15 at 7:49
  • 1
    $\begingroup$ You should check out Páidí Creed's PhD thesis. Your question is a great one but I think it's too broad for this site. I think it should be easy to prove that your method can produce every possible Eulerian graph with two odd-degree vertices. However, if it does generate them uniformly, proving that is likely to be too much for a Stack Exchange answer. You've essentially set up a Markov chain and you'd need to prove that its stationary distribution is uniform and that it reaches that distribution reasonably quickly. That's several pages of work. $\endgroup$ – David Richerby Aug 20 '15 at 7:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.