edited by
6,475 views
54 votes
54 votes

An undirected graph is complete if there is an edge between every pair of vertices. Given a complete undirected graph on $n$ vertices, in how many ways can you choose a direction for the edges so that there are no directed cycles?

  1. $n$
  2. $\frac{n(n-1)}{2}$
  3. $n!$
  4. $2^n$
  5. $2^m, \: \text{ where } m=\frac{n(n-1)}{2}$
edited by

7 Answers

Best answer
76 votes
76 votes

They are asking to convert Complete Undirected graph into Directed graph without cycle by choosing direction for the edges.

See this $K_{3}$ graph-

 

(Image ref)

By this time you must have got the problem statement meaning- our resultant graph should be acyclic.

Lets say we have a complete graph $G$ which has $n$ vertices, $v_1, v_2,\dots v_n$. To convert it into the resultant graph we have to assign direction to each edge. Now see, our resultant graph is acyclic therefore it must have a topological order.

(I have not drawn all edges except $V_1$ edges.)

here every rearrangement of vertices in topological sort leads to one particular combination to choose the direction of edges.

Hence - $n!$ is answer.

Just to illustrate more, see one of the permutation out of $n!$

These two permutation shows that undirected edge between $V_1$ and $V_2$, was first chosen as $V_1 \rightarrow V_2$ and then $V_2 \rightarrow V_1$

Don't think about the labeling of vertices, If I do unlabelling of all $n!$ permutations then all structures are same. But it doesn't matter If I am arriving at the same structure, What matters is, In how many ways I can reach to that.

See this-

 

All the above $3$ structures are Isomorphic. But still, there are $3!$ ways to reach such structure.


Let there be $3$ vertices,

In how many ways we can arrage them? It is $3! = 6$

  1. $a,b,c$
  2. $a,c,b$
  3. $b,a,c$
  4. $b,c,a$
  5. $c,a,b$
  6. $c,b,a$

Let's take each order, and check in how many ways we can make it as directed edges ( remember there are 3 edges in K3 ) with it

ex :- $b,a,c:$  we make $b \to a \to c.$ Now the remaining edge must be $b \to c;$ there is no other possibility for it, as if we make $c \to b$ then it is cyclic.

So, there is only one way to assign edges, to each order !

Now, you got doubt that " There may be many assignment of direction of edges than permutations ? "

Answer for this question is, Should be NO. ( think about it, let there be an edge $u \to v,$ then $u$ should be before $v$)

In how many ways we can choose direction for the edges so that there are no directed cycles? $\to$ Number of permutations of vertices $= n !$

Correct Answer: $C$

edited by
23 votes
23 votes
Let there are $n$ vertices $a_{1},a_{2},...,a_{n}$. If edge from any vertex direct to previously/already paved vertex it forms a cycle. To ensure it doesn't happen at every vertex there would be a choice of the edge such that it would direct the vertices not yet encountered. Therefore the number of ways turned out to be $n*(n-1)*(n-2)*...*1 = n!$.
19 votes
19 votes

Take the example of a triangle (K3) where n = 3.

We can have total of 8 permutations - since each edge can be filled with two options ' > ' or ' < ' => 2 * 2 * 2 = 8.

We can have a cycle only in two permutations  =>  ' > > > ' and ' < < < '.

And hence, it is 8-2 = 6 when there are no directed cycles. This corresponds to only option (c), and no other option. 

5 votes
5 votes
Draw two directed graphs, one having 3 vertices and other having 4 vertices (Draw such that there are no directed cycles)

You will notice,

In graph with 3 vertices, there is one vertex with indegree 2, one vertex with indegree 1 and one vertex with indegree 0

That is, 3*2*1 different ways to choose vertices $\Rightarrow 3! ways$

Similarly in graph with 4 vertices, there will be 1 vertex of indegree 3, one with indegree 2, one with indegree 1 and final one with indegree 0

That is 4*3*2*1 different ways $\Rightarrow 4! ways$

 

Similarly for n vertices n! ways
Answer:

Related questions

37 votes
37 votes
4 answers
3