Is there a way to count the number of Hamiltonian circuits that exist in a graph?
4 次查看(过去 30 天)
显示 更早的评论
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 个评论
Christine Tobler
2019-1-29
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.
回答(1 个)
John D'Errico
2019-1-29
编辑:John D'Errico
2019-1-29
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 个评论
John D'Errico
2019-1-29
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.
另请参阅
类别
在 Help Center 和 File Exchange 中查找有关 Construction 的更多信息
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!