search
Log In
41 votes
3.1k 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}$
in Graph Theory
edited by
3.1k views
0
n! ?
0
@arjun Sir , @experienced folks what should i do if i cant solve these type of questions ie having a diificulty in counting/ permutations and combinarions.
1

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

2
Ans should be n! ....best approach is to draw graph with specifications given in question
0
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?

6 Answers

65 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 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
0
Nice explanation.Thanks :-)
0
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?
0

@Tiger12345 In this question it is mentioned that there should be no directed cycles. According to your logic we will get directed cycles also.

19 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!$.
0
He is talking abt topological structure which is mentioned in best answer ...
0
Constructive prooproof
0
Constructive prove.
5
Think of deadlocks. A condition that needs to be satisfied for deadlocks is circular wait. To eliminate circular wait, there's some method (can't recall it's name) in which we number each process and each resource, and if a resource is allocated to a process, then the process can ask for only those resources that are numbered higher than the currently held resource. This diasbles circular wait, as we can't go in a loop — we'll always point forward.

 

Similarly here, label each vertex as 1,2,3,4... At each point a vertex can point to only a larger numbered vertex. (If it points to a smaller numbered, we'll get a loop).

 

So, $n!$
16 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. 

1
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?"
2
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.
1
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
1

Soumya29 no directed cycle of any length

4 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
1 vote
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.
0 votes

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

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

Answer:

Related questions

13 votes
2 answers
1
1.2k views
For an undirected graph $G=(V, E)$, the line graph $G'=(V', E')$ is obtained by replacing each edge in $E$ by a vertex, and adding an edge between two vertices in $V'$ if the corresponding edges in $G$ are incident on the same vertex. Which of ... maximum degree of any vertex in the line graph is at most the maximum degree in the original graph each vertex in the line graph has degree one or two
asked Dec 23, 2016 in Graph Theory jothee 1.2k views
22 votes
2 answers
2
1.4k views
A vertex colouring of a graph $G=(V, E)$ with $k$ coulours is a mapping $c: V \rightarrow \{1, \dots , k\}$ such that $c(u) \neq c(v)$ for every $(u, v) \in E$. Consider the following statements: If every vertex in $G$ has degree at most $d$ then ... Which of the above statements is/are TRUE? Choose from the following options: only i only i and ii only i and iii only ii and iii i, ii, and iii
asked Dec 23, 2016 in Graph Theory jothee 1.4k views
33 votes
4 answers
3
2k views
A vertex colouring with three colours of a graph $G=(V, E)$ is a mapping $c: V \rightarrow \{R, G, B\}$ so that adjacent vertices receive distinct colours. Consider the following undirected graph. How many vertex colouring with three colours does this graph have? $3^9$ $6^3$ $3 \times 2^8$ $27$ $24$
asked Dec 23, 2016 in Graph Theory jothee 2k views
7 votes
1 answer
4
613 views
Consider the following program modifying an $n \times n$ square matrix $A$: for i=1 to n: for j=1 to n: temp=A[i][j]+10 A[i][j]=A[j][i] A[j][i]=temp-10 end for end for Which of the following statements about the contents of matrix $A$ at the end of this program must be TRUE? ... by $10$ the new matrix $A$ is symmetric, that is, $A[i][j]=A[j][i]$ for all $1 \leq i, j \leq n$ $A$ remains unchanged
asked Dec 22, 2016 in Algorithms jothee 613 views
...