209k views
1 vote
Consider the vertex set V={v1​,…,vn​}. How many distinct directed graphs exist that have V as their vertex set?

1 Answer

7 votes

Final answer:

The number of distinct directed graphs that can be formed with a vertex set V={v1,...,vn} is 3^n(n-1), reflecting the number of edge possibilities between every pair of vertices.

Step-by-step explanation:

The student's question is: How many distinct directed graphs exist that have V as their vertex set, where V={v1, ..., vn}? In a directed graph, each pair of vertices can have up to two distinct edges between them: one for each possible direction (from vi to vj and from vj to vi). Since there are n vertices, there are n(n-1) possible pairs of vertices (excluding loops from a vertex to itself). For each pair of vertices, there are 2 possible edges (one in each direction) and also the possibility of having no edge, which gives us 3 choices per pair. Thus, the total number of directed graphs is 3n(n-1).

User Stux
by
7.1k points