How to generate graphs with a Hamiltonian path?

1
votes

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 then I can decide whether a 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 graph has always Hamiltonian path.

In addition, my graph has two meet two specific condition

  • vertices can only have 2,3 or 4 edges.
  • possible number of vertices follows this sequence: 6, 10, 15, 20, 25...n-5, n where n % 5 = 0

Could you explain me how should I start and which way I should follow to achieve this easily?

1
c#graphgraph-theory
have you tried something? anything that makes it hard to do this? - Batavia
you might take a look at the msdn section on graphs msdn.microsoft.com/en-us/library/ms379574(v=vs.80).aspx - Batavia
explain how to start is a bit nebulous. Given your tags, a valid answer to that could be "read a book on C# programming and take a course in discrete math". What you you seem to really be looking for though is either a discussion or a pre-written function, neither of which is supported by stack overflow. It's best that you make some programming effort first, then post asking for help with what you've already got written. - mah
@Batavia this perfect start for generating the graph. But How could I know whether there is a Hamiltonian Path, or not? - user2337191
@mah you are right. I will remove the question 5 minutes later. It just seemed too complicated. I couldn't even start. The only thing I want, I don't want to check whether there is hamiltonian path or not. All the generated graphs should already have it. - user2337191

1 Answers

0
votes

If you want to make sure that your graph has a Hamiltonian path, start by creating a graph that consists of a single path connecting all vertices. This is going to be your Hamiltonian path.

Hamiltonian Path

Once the edges of the Hamiltonian path are added to the graph, proceed by generating additional edges connecting pairs of random vertices, until you satisfy the additional conditions on your graph.

Finished graph

The result is guaranteed to have a Hamiltonian path, because your initial graph has it.