3
$\begingroup$

I'm trying to practice some combinatorics and I faced this problem, let's say we have given graph with N nodes and M edges. $$N\leq500, M \leq N\cdot(N - 1)/2$$

In this graph I want to count the sub-sets of edges such that each subset will have exactly $N-1$ edges and the edges forming the subset will form connected graph.

Example

Let's say we have the following graph

Graph

We can count a total of 3 subsets: {1,2,3,5}, {1,2,3,4}, {1,2,4,5}. Please note the the numbers from 1 to 5 are marking the edges, not the nodes.

What I think

Let's say our graph is complete graph, it is the worse case. If we have 500 nodes and 499 nodes going out from each node, I think that there could be $500^{500}$ possible combinations which is huge number.

$\endgroup$
  • $\begingroup$ It's not quite as bad, since we're drawing without replacement here. $\endgroup$ – Raphael Aug 1 '17 at 14:07
3
$\begingroup$

There is a simple algebraic algorithm based on the Matrix Tree Theorem. Just make the Laplacian matrix of the graph and compute $N^{-1}$ times the product of its non-zero eigenvalues.

$\endgroup$
  • $\begingroup$ I found this answer truly intriguing (but not incorrect) could you please elaborate It a little bit more? $\endgroup$ – Carlos Linares López Aug 3 '17 at 13:26
  • $\begingroup$ The Wikipedia article has an worked example. What else do you want to see? $\endgroup$ – Louis Aug 3 '17 at 13:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.