Is there a way to count the number of Hamiltonian circuits that exist in a graph?

Question

badscience 2019-1-29

0
链接

此问题的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/441982-is-there-a-way-to-count-the-number-of-hamiltonian-circuits-that-exist-in-a-graph

评论： John D'Errico 2019-1-29

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.

badscience 2019-1-29

Interesting. The purpose of wanting to find the number of Hamiltonian paths is actually to calculate the number of permutations that exist for a specific type of tableau related to Young tableaux. As it stands, I have a script that brute force calculates all available tableaux for a given value of n (the number of noded that end up in the graph) and then does a check on each permutation and picks out the "valid" permutations based on a set of rules. But this gets very memory intensive as you can imagine because before it can find the valid tablueax, it has to create n! permutations. And I think there are, for examlple, only 512 valid tableaux in all of the 10! permutations for n=10. So it is very inneffiecient.

My hopes were that applying graph theory to this problem would increase the efficiency by constructing the tableaux based on the number and structure of these paths but from what I am gathering, this may not be the way to tackle this after all.

Thanks for the response!

请先登录，再进行评论。

请先登录，再回答此问题。

Answer 1

John D'Errico 2019-1-29

1
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/441982-is-there-a-way-to-count-the-number-of-hamiltonian-circuits-that-exist-in-a-graph#answer_358590

编辑：John D'Errico 2019-1-29

在 MATLAB Online 中打开

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 个评论
显示无隐藏无

badscience 2019-1-29

Thanks for this, though I have actually already begun writing a recursion loop that hopefully will build the necessary permutations using these patterns. The reason I asked this question seperately (I think you were the one that pointed out the graph theory approach on my other question) is now simply out of curiosity. I think that approaching the problem from this graph theory method would be a neat and slick way of solving this!

But this answer here is already how I have begun tackling the problem. I just wanted to see if there was some slick method to figuring out this graph theory approach to satisfy my own curiosity! :) So far through my own attempts and research at calculating the number of hamiltonian paths, it is looking like there may be a little more to it than meets the eye, but I find it interesting nonetheless!

Thanks for all your assistance here though, you have been a huge help!

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.

请先登录，再进行评论。