Q. With V(greater than 1) vertices, how many edges at most can a Directed Acyclic Graph possess?

View solution

Q. The topological sorting of any DAG can be done in ________ time.

View solution

Q. If there are more than 1 topological sorting of a DAG is possible, which of the following is true.

View solution

Q. Which of the given statement is true?

View solution

Q. 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?

View solution

Q. What is the value of the sum of the minimum in-degree and maximum out-degree of an Directed Acyclic Graph?

View solution

Q. In which of the following does a Directed Acyclic Word Graph finds its application in?

View solution

Q. What is time complexity to check if a string(length S1) is a substring of another string(length S2) stored in a Directed Acyclic Word Graph, given S2 is greater than S1?

View solution

Q. In which of the following case does a Propositional Directed Acyclic Graph is used for?

View solution

Q. Every Binary Decision Diagram is also a Propositional Directed Acyclic Graph.

View solution

Q. In a Propositional Directed Acyclic Graph Leaves maybe labelled with a boolean variable.

View solution

Q. Given Adjacency matrices determine which of them are PseudoGraphs?

i) {{1,0} {0,1}}

ii) {{0,1}{1,0}}

iii) {{0,0,1}{0,1,0}{1,0,0}}

View solution

Q. All undirected Multigraphs contain eulerian cycles.

View solution

Q. Determine the number of vertices for the given Graph or Multigraph?
G is a 4-regular Graph having 12 edges.

View solution

Q. Which of the following statement is true.

View solution

Q. Given Adjacency matrices determine which of them are PseudoGraphs?
i) {{1,0} {0,1}}

ii) {{0,1}{1,0}}

iii) {{0,0,1}{0,1,0}{1,0,0}}

View solution

Q. Possible number of labelled simple Directed, Pseudo and Multigarphs exist having 2 vertices?

View solution

Q. Which of the following is a HyperGraph, where V is the set of vertices, E is the set of edges?

View solution

Q. What would be the Incidence Matrix of the given HyperGraph?
V = {x,y,z} E = {{x,y}{y}{x,z}{z,y}}

View solution

Q. What is the degree sequence of the given HyperGraph, in non-increasing order.
V = {v1,v2,v3,v4,v5,v6} E = {{v1,v4,v5} {v2,v3,v4,v5} {v2} {v1} {v1,v6}}

View solution