Recent questions tagged directed-acyclic-graph

Suppose DFS is called on a DAG $G$, and the resulting DFS forest has a single tree. Then $G$ has exactly one source vertex.True False

Let $G$ be a weighted directed acyclic graph with $m$ edges and $n$ vertices. Given $G$ and a source vertex $s$ in $G$, which one of the following options gives the worst...

directed acyclic graph(DAG)is a simplified step from the AST. Solve the following expressions by AST and DAG: X=(((a+a))+((a+a)+(a+a)))

Number of nodes in the DAG(Directed Acyclic Graph) representing (a+b)+c+(a+b)

​​​​​​Consider the directed acyclic graph (DAG) below:Which of the following is/are valid vertex orderings that can be obtained from a topological sort of the DAG?$\text{...

Which of the following does not define a tree?A tree is a connected acyclic graph.A tree is a connected graph with $n-1$ edges where ' $n$ ' is the number of vertices in ...

how many topological sort possible for above graph?directions like this question https://gateoverflow.in/39669/gate-cse-2016-set-1-question-11

What is the minimum number of nodes required in a DAG (Directed Acyclic Graph) for the following block?\[\begin{aligned}U=Z & =V+W \\X=Y & =U+1 \\A & =X+Y\end{aligned}\]

Consider a DAG $\mathrm{G}=(\mathrm{V}, \mathrm{E})$ which has topological ordering of vertices $v_1, v_2, \ldots ,v_n$. We want to count number of paths from vertex $v_i...

Which of the following is not true for tree and graph?A tree is a graphA graph is a treeTree can have a cycleTree is a $\text{DAG}$

The graph that shows basic blocks and their successor relationship is called:DAGControl graphFlow graphHamiltonian graph

Construct the DAG and identify the value numbers for the subexpressions of the following expressions, assuming $+$ associates from the left.$a+b+(a+b)$$a+b+a+b$$a+a+((a+a...

Construct the DAG for the expression$((x + y)-((x + y)\ast(x -y))) + ((x+y)\ast(x-y))$

I have trouble understanding the difference between DAG and Multi-stage graph. I know what each of them isBut I think that a multi-stage graph is also a DAG. Are multi-st...

b = b + cd = b + db = b – de = d + bThe minimum number of nodes and edges present in the DAG representation of above basic block respectively are ?4 and 55 and 46 and 66 ...

Consider the basic block given below:u=u+vv=v+wx=v-wy=v-xz=u+vThe minimum number of nodes and edges present in the DAG representations of the above basic block respective...

Question.Construct the Dag for the following Assume that + is left associative?a)a+b+(a+b)b)a+b+a+bc)a+a+(a+a+a+(a+a+a+a))Please give the Answer to these questions?????