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
0 comments:
Post a Comment
Let us know your responses and feedback