## How many graphs?

Let's talk about algorithms!

Moderator: Board moderators

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

### How many graphs?

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?

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

### Re: How many graphs?

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):

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

### Re: How many graphs?

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?

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