Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Does any body who has good back ground in graph theory tells me that how many possible directed graphs will be there with $N$ vertices and $E$ edges. I need all the possible combinations even even isomorphic graphs also.

share|improve this question

migrated from stackoverflow.com Dec 26 '11 at 22:25

This question came from our site for professional and enthusiast programmers.

1 Answer 1

up vote 2 down vote accepted

If you treat isomorphic graphs separately, then one way to think about this is as follows. If you start off with $N$ nodes and want $E$ edges, you could build a graph by considering an $E$-element subset of the set of all possible edges in the graph. The number of possible edges is $N^2$, since each node can be connected to each other node (including itself), so the number of ways you can pick $E$ of these edges is $\binom{N^2}{E}$. This is

$$ \frac{(N^2)!}{(E!) \cdot (N^2 - E)!}, $$

which is a staggeringly huge number.

Hope this helps!

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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