Page 1 of 1

How many graphs?

Posted: Sun Jan 04, 2009 7:48 pm
by JohnTortugo
How many different graphs are with V vertex?

The graph should be: Directed, connected, with no self-loops and no "parallel-edges" (namely the same start-point and end-point).

I'm trying to solve this problem for a long long time...

I really would appreciate if someone can point me some hint.

PS: The problem was in a online contest, and I wasn't able to find it again.

Thanks in advance, John.

Re: How many graphs?

Posted: Sun Jan 04, 2009 8:10 pm
by mf

Re: How many graphs?

Posted: Mon Jan 05, 2009 9:48 pm
by maxdiver
How could the directed graph be connected? I am not familiar with such a term (for example, is graph 1->2 connected or not? you can't go from 2 to 1)

I know the solution for undirected graphs (connected and without loops and parallel edges), it's described on my site (it's in Russian, but I hope Google translator is enough to get an idea):
http://translate.google.com/translate?h ... e0=&swap=1

Re: How many graphs?

Posted: Mon Jan 05, 2009 10:05 pm
by mf
maxdiver wrote:How could the directed graph be connected?
Probably he meant strong connectivity by that.

Another possible notion of connectivity in digraphs is weak connectivity - when for each pair of vertices u, v, there's either a path from u to v, or a path from v to u, or both.

Re: How many graphs?

Posted: Tue Jan 06, 2009 3:41 pm
by JohnTortugo
Thanks mf and maxdiver, these links point me for what I was looking for.