How many graphs?

Let's talk about algorithms!

Moderator: Board moderators

Post Reply
JohnTortugo
New poster
Posts: 18
Joined: Sun Jul 20, 2008 7:05 pm

How many graphs?

Post by JohnTortugo » Sun Jan 04, 2009 7:48 pm

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.

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Re: How many graphs?

Post by mf » Sun Jan 04, 2009 8:10 pm


maxdiver
Learning poster
Posts: 51
Joined: Tue Sep 04, 2007 2:12 pm
Location: Russia, Saratov
Contact:

Re: How many graphs?

Post by maxdiver » Mon Jan 05, 2009 9:48 pm

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

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Re: How many graphs?

Post by mf » Mon Jan 05, 2009 10:05 pm

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.

JohnTortugo
New poster
Posts: 18
Joined: Sun Jul 20, 2008 7:05 pm

Re: How many graphs?

Post by JohnTortugo » Tue Jan 06, 2009 3:41 pm

Thanks mf and maxdiver, these links point me for what I was looking for.

Post Reply

Return to “Algorithms”