With V(greater than 1) vertices, how many edges at most can a Directed Acyclic Graph possess?(a) (V*(V-1))/2(b) (V*(V+1))/2(c) (V+1)C2(d) (V-1)C2Enquiry is from Directed Acyclic Graph topic in division Graph of Data Structures & Algorithms IThe question was posed to me during an interview for a job.

With V(greater than 1) vertices, how many edges at most can a Directed

1.	With V(greater than 1) vertices, how many edges at most can a Directed Acyclic Graph possess?(a) (V(V-1))/2(b) (V(V+1))/2(c) (V+1)C2(d) (V-1)C2Enquiry is from Directed Acyclic Graph topic in division Graph of Data Structures & Algorithms IThe question was posed to me during an interview for a job.
Answer» The correct answer is (a) (V(V-1))/2 Easiest EXPLANATION - The first edge WOULD have an OUTGOING degree of atmost V-1, the next edge would have V-2 and so on, hence V-1 + V-2…. +1 equals (V(V-1))/2.

Discussion

No Comment Found

Related InterviewSolutions

In a Propositional Directed Acyclic Graph Leaves maybe labelled with a boolean variable.(a) True(b) FalseWhat is the answer to this question? I'm confused
What is the number of words that can be formed from the given Directed Acyclic Word Graph?(a) 2(b) 4(c) 12(d) 7Please answer it as soon as possible.
For any two different vertices u and v of an Acyclic Directed Graph if v is reachable from u, u is also reachable from v?(a) True(b) False
Which of the following logical operation can’t be implemented by polynomial time graph manipulation algorithms using Binary Decision Diagrams?(a) Conjunction(b) Disjunction(c) Negation(d) Tautology CheckingI'd like to ask this question from Binary Decision Diagrams &And Inverter Graph in section Graph of Data Structures & Algorithms IThe question was asked in a job interview.
The And Inverter Graph representation of a Boolean function is more efficient than the Binary Decision Diagram.(a) True(b) FalseThis intriguing question originated from Binary Decision Diagrams &And Inverter Graph in section Graph of Data Structures & Algorithms IThis question was addressed to me in a national level competition.
And Inverter Graph is a type of __________(a) Multigraph(b) Cyclic Graph(c) Directed Acyclic Graph(d) Directed Acyclic Word GraphI want to ask this question from Binary Decision Diagrams &And Inverter Graph in chapter Graph of Data Structures & Algorithms IThis question was addressed to me in examination.
Size of an And Inverter Graph is the number of _______ gates and the number of logic levels is number of ________ gates on the __________ path from a primary input to a primary output.(a) AND, AND, average(b) AND, OR, longest(c) OR, OR, shortest(d) AND, AND, longestMy enquiry is from Binary Decision Diagrams &And Inverter Graph in portion Graph of Data Structures & Algorithms IThis question was posed to me in an online quiz.
Two or more And Inverter Graphs can represent same function.(a) True(b) FalseThis intriguing question originated from Binary Decision Diagrams &And Inverter Graph topic in portion Graph of Data Structures & Algorithms IThis question was addressed to me in homework.
How many nodes are required to create a Binary Decision Tree having 4 variables?(a) 2^4(b) 2^4-1(c) 2^5(d) 2^5-1Asked question is from Binary Decision Diagrams &And Inverter Graph topic in portion Graph of Data Structures & Algorithms II got this question in quiz.
In a Binary DecisionDiagrams 0 values by a _________ line and the 1 values are represented by a _________ line.(a) dashed, bold(b) bold, dashed(c) dotted, bold(d) dotted, dashedI want to ask this question from Binary Decision Diagrams &And Inverter Graph in chapter Graph of Data Structures & Algorithms IThe question was posed to me during an internship interview.

Discussion

No Comment Found

Related InterviewSolutions

Reply to Comment