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:
- Create a chain, by definition it is a eulerian path. With exactly 2 odd degree nodes.
- 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.
- 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?