The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+17 votes
514 views

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}$
asked in Graph Theory by Veteran (99.2k points)
edited by | 514 views
n! ?

3 Answers

+9 votes
Best answer

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 Problem statement meaning. Your resultant graph should be acyclic.

Lets say you 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 topological order.

(I have not drawn all edges except V1 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 these structures are Isomorphic...But still, there are $3!$ ways to reach such structure.

C.

answered by Veteran (12.8k points)
edited ago by
Nice explanation.Thanks :-)
+5 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. 

answered by Active (1.3k points)
I have a confusion. It's may be silly.

In the question, they mean to say that the resulting graph should not contain directed cycle "with n vertices" or "it should not contain any directed cycle.Means even the directed cycle with less than n vertices?"
If cycle length is "n", then there will be always 2 ways to form a cycle, right? '>>>...>' OR '<<<..<<'. Then the answer would have been 2^n-2, which is not in the options.
yes, u r right , in question its saying that there would be no cycle either of n length as well as  of less than n , but k3 is the simple and small example to check which will give n!, it means its applicable for all graph either k4,k5or so on
+3 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!$.
answered by Boss (5.6k points)


Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

29,157 questions
36,985 answers
92,166 comments
34,824 users