0
$\begingroup$

As an example, if I have 2 vertices V1, V2. All the possible directed graphs ( there can be indegree 0 vertices as well) are 3 {{V1,V2}, {V1->V2}, {V1<-V2}}. But, when there are 3 vertices all the possible graphs are found to be very large. {{V1,V2,V3}, {V1->V2,V3}, {V1<-V2,V3}.....{V1->V2->V3} .... } . Like

  1. graphs with edges 0
  2. graphs with 1 edges and their directionality changed
  3. graphs with 2 edges and their directionality changed
  4. graphs with 3 edges and there directionality changed

My attempt so far: As mentioned above I simply analyze the questions, but it is found to be growing larger. I was able to found that for any N no. of vertices, all the possible edges ( undirected ) are N*(N-1) /2. It is like I have to analyze all the number of possible edges and their directionality.

But, which is not clear is the possible number of graphs is growing with a possible number of edges. I would appreciate any suggestions on how to obtain all the possible directed graphs from N number of vertices.

$\endgroup$
2
$\begingroup$

There are $\binom{V}{2}=V(V-1)/2$ distincy pairs of vertices. For any pair of vertices $\{u,v\}$, any one of the 3 options can hold:

  1. Either there is no edge between $u$ and $v$
  2. There is an edge directed from $u$ to $v$
  3. There is an edge directed from $v$ to $u$

Hence total number of directed graphs on $V$ vertices is $3^{V(V-1)/2}$.

$\endgroup$
1
$\begingroup$

With $N$ vertices, there are $N_E = \binom{N}{2}$ possible edges. We can then get $\binom{N_E}{m}$ many undirected graphs with $m$ edges. Each edge has 2 possible directions giving $2^m\times\binom{N_E}{m}$ possible directed graphs with $m$ edges (because each undirected graph has $2^m$ possible orientations). Summing everything, you get $\sum_{m=0}^{N_E}\binom{N_E}{m}2^m = 3^{N_E} = 3^\binom{N}{2}$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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