Is there a way to count the number of Hamiltonian circuits that exist in a graph?
4 visualizaciones (últimos 30 días)
Mostrar comentarios más antiguos
I am generating matricies, G, that describe the edges of a graph. I am hoping to count how many hamiltonian circuits exist for a graph generated for a given value of 'n'.
n=input('Input value of n\n')
G = triu(ones(n),-1) - eye(n)
A = digraph(G);
plot(A)
I have tried using a few functions written by other users, though all of these functions I have found just find a singular hamiltonian circuit and then terminate. I don't yet have the knowhow to generate my own function or algorithm to accomplish this goal. I want to be able to find the number of hamiltonian circuits that exist for each generated graph. Are there any functions or algorithms that make this possible?
2 comentarios
Christine Tobler
el 29 de En. de 2019
There are no out-of-the box algorithms in MATLAB that do this.
According to the Wikipedia page Hamiltonian path problem, this is a hard problem and while there are several algorithms proposed, they will all be quite slow as the number of nodes in the graph grows.
If you have a very small graph (up to 10 nodes), it might be easiest to do a brute-force algorithm: For every permutatio of the nodes in G (compute using perms(1:numnodes)), check if it is a valid path in the graph (that is, whether all edges in this cycle of nodes exist). The number of valid paths is the number of Hamiltonian cycles multiplied by numnodes.
A slightly smarter version would only compute perms(2:numnodes), and specify that the first node in the cycle should always be 1 - this will remove some duplicates.
Respuestas (1)
John D'Errico
el 29 de En. de 2019
Editada: John D'Errico
el 29 de En. de 2019
Well, you are trying to do this. Making an effort is important.
Sometimes it becomes necessary to try some numbers out.
n = 1;
n = n + 1;[n,sum(all(diff(perms(1:n),[],2)>= -1,2))]
ans =
2 2
n = n + 1;[n,sum(all(diff(perms(1:n),[],2)>= -1,2))]
ans =
3 4
n = n + 1;[n,sum(all(diff(perms(1:n),[],2)>= -1,2))]
ans =
4 8
n = n + 1;[n,sum(all(diff(perms(1:n),[],2)>= -1,2))]
ans =
5 16
Now, think about what you see. Do you see a pattern?
A simple pattern is not enough to form a conclusion. But SOMETIMES, a pattern is an important clue.
Now, consider if there is a reason behind that. A good way to do this is another investigative step. Actually generate all of those permutations. Start with the problem for 1:2. List all the valid permutations. Now, suppose you added one more number, the number 3 to that set. Where could it go? THINK! I won't do your homework for you.
So start at n=2. There are exactly TWO valid permutations.
[1 2] and [2 1]
Where could you add the number 3? Do you see there are EXACTLY 2 places it can go for each of the above permutations, and never more than that?
Now you should have by far enough information to finish your homework. In fact, I probably gave you too much of a hint. Oh well.
2 comentarios
John D'Errico
el 29 de En. de 2019
Actually, if all you want to do is count the set, then inductive reasoning is sufficient, IF you see why it applies.
That is, given the set of all valid permutations of order n, where can you now insert the number n+1? Once you see that, you are literally done. Well, you still need to solve the resulting recursion to yield the fully general term.
Ver también
Categorías
Más información sobre Construction en Help Center y File Exchange.
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!