Cheap and Secure Web Hosting Provider : See Now

[Solved]: How to generate graphs with a Hamiltonian path?

, , No Comments
Problem Detail: 

I need to create a graph generator for my next project. Generally algorithms are trying to find a Hamiltonian path in a graph. So I can create a graph generator, generate a graph, and then I can decide whether the graph has a Hamiltonian path or not. If not, I can regenerate the graph but this is not a cool way.

I want my generated graphs that always have a Hamiltonian path. My graph has two additional conditions:

  • Vertices can only have 2, 3, or 4 edges.
  • Possible number of vertices follow the sequence 6, 10, 15, 20, 25...n-5,n where n % 5 = 0.

How should I start, and how do I achieve this easily?

Asked By : Always Newbie

Answered By : Juho

The simplest solution is the one suggested by Yuval Filmus. That is, take a simple path on $n$ vertices, and finish the construction after you have added some number of edges. Clearly, it is easy to enforce the maximum degree condition as well.

Alternatively, you could generate graphs whose structure guarantees the existence of a Hamiltonian path. For example, as shown by Tutte, every 4-connected planar graph has a Hamiltonian path (see e.g., Wikipedia for the statement). Then, a high-performance tool for generating planar graphs is plantri. My feeling is that this is unnecessarily complicated for your use case, but it gives you a possible another approach you might be interested in later on.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/50937

 Ask a Question

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback