TIFR CSE 2017 | Part B | Question: 12

Question

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?

• A. $n$
• B. $\frac{n(n-1)}{2}$
• C. $n!$
• D. $2^n$
• E. $2^m, \: \text{ where } m=\frac{n(n-1)}{2}$

Comments

paraskk

take any arbitrary value of n.

I've taken n = 3,and form cycles according to qsn. you will get a value & then match the value wth the given option

---

Ans should be n! ....best approach is to draw graph with specifications given in question

---

Can anyone tell me why it can't be 2^n(n-1)/2 since any edge can have direction right or left so we can chose it 2 ways?

Answer 1

A  cycle will be formed when the no of vertices is greater than  2. So for a complete graph with 3 vertices has 3 edges.

Lets denote f(n=3) as no of acyclic graphs possible with 3 nodes.

So  for 3 edges there are 2^3 possible directions ">" or " <" for each edge. But all "> "  or all "<" will give cycle.

Now f(3)=2^3-2=6

Since a graph is acyclic   iff  it maintains topological order. So

f(4)= 4C1*f(3) because choose any of 4 nodes and maintain topological order with remaining 3 vertices. So f(4)= 4*6= 24= 4!

Similarly f(5)= 5C1*f(4)= 5*4!=5!

So f(n)= n!.

Correct me if i have made any error.

Answer 2

For vertex 1 , we have 6 choices , similarly we have 4 different choices for every vertex, which makes 24 ways. which is 4! for K_{4 .} 

Kindly Correct me if I'm wrong somewhere. Thank U

Answer 3

This question certainly needs prior knowledge. It will be very hard to come with the logic in exam.

When is a cycle possible in a graph?

Whenever there is a back_edge in the DFS traversal of the graph.

So how do we avoid it?

Convert every edge except the tree_edges as forward_edge.

How many can we do a DFS traversal of a complete graph i.e. to fix the direction of tree edges?

$n!$ ways.

How many ways can we make rest of the edges as forward_edge?

Of course only 1 way.

 

Therefore total $n! * 1 = n! \: ways$ to make graph acyclic