Counting connected graphs
I'm trying to count the number of simple connected graphs with exactly K edges and N clearly marked vertices. I wrote this code below, but it doesn't work.
The idea is that this kind of graph will not have isolated points, so I will do this for N vertices and K edges.
Connected(N,K):
1) Total = all possible graphs, including disconnected ones.
2) Disconnected = Sum from i=1 to i=N-1 [(Connected(i,K)*(number of ways to
choose i vertices from all N vertices)]
3) return Total-Disconnected
Python code:
#c dict just stores previous combinations
c = {}
def answer(N, K):
ways = connected(N, K)
return str(ways)
#number of simple graphs using exactly n vertices and k edges. no isolated vertices
def connected(n, k):
if k < n-1:
return 0
edges = n*(n-1)/2
if k > edges:
return 0
#number of all possible graphs with n vertices and k edges
ways = choose(edges, k)
#subtract number of graphs that are not connected
for i in range(1, n):
ways -= connected(i, k)*choose(n, i)
return ways
#calculates nCk
def choose(n, k):
key = str(n)+","+str(min([k,n-k]))+"/"+str(max([k,n-k]))
if key in c:
return c[key]
else:
top = fact(n)
bottom = fact(k)*fact(n-k)
ans = top/bottom
c[key] = ans
return ans
#factorial
def fact(num):
ret = 1
for i in range(2,num+1):
ret *= i
return ret
source to share
Your formula for Disconnected is actually wrong.
Let denote the vertices 1, 2, ..., N. In your formula, the term:
[(Connected (i, K) * (number of ways to select i vertices from all N vertices)]
It is assumed thatcalculates the number of graphs so that the connected component of vertex 1 contains i vertices. But this product only gives the number of possible connected components. For each such choice of a connected component, there are still many ways of placing edges between the remaining (N - i) vertices.
To get the correct formula, you must also consider the number of edges in the connected component.
Let Conn (i, j) be the number of connected graphs with i labeled vertices and exactly j edges. Then we have:
select (N * (N - 1) / 2, K) = sum (i = 1 - N, j = 0 - K) select (N - 1, i - 1) * Conn (i, j) * select (( N - i) * (N - i - 1) / 2, K - j)
The left side is the total number of graphs with N vertices and K-edges. The summand on the right-hand side is the number of graphs with N vertices, K-edges, and such that the connected component of vertex 1 has i vertices and j edges.
Further explanation of the term: first, select i - 1 vertices from N - 1 vertices other than vertex 1, then multiply by the number of ways to form a connected graph with i vertices and j edges, and finally add any K - j edges from the remaining N - i peaks.
From this formula, you will be able to write a DP algorithm to calculate all numbers Conn (i, j).
While this may be slow, it gives the correct answers. You can think about better algorithms later.
source to share