Practice Topological Ordering Of Directed Acyclic Graphs (dag) (24.1) - Topological Ordering of Directed Acyclic Graphs (DAG)

Practise this section

9 questions

Flashcard drill
2 cards from this section. Quick, good the night before a test.
Exercise
6 questions · about 4 min · pass mark 70%. Hints available.
Sign up to start the exercise
Quiz
3 questions · about 2 min · pass mark 70%. Hints available.
Sign up to start the quiz

6 sample questions

Question 1.
What is the in-degree of a vertex?
Show hintHide hint
Think about how many arrows point to the vertex.
Question 2.
What type of graph is necessary for topological sorting?
Show hintHide hint
Remember the acronym DAG!
3Question 3.
What does 'in-degree' refer to in a directed graph?
- Count of outgoing edges
- Count of incoming edges
- Total edges
Show hintHide hint
Think about the arrows pointing towards the vertex.
4Question 4.
True or False: A graph must be acyclic to perform a topological sort.
- True
- False
Show hintHide hint
Consider the definition of a DAG.
Question 5.
Given a DAG with vertices A, B, C, and edges A->B, A->C, B->C, what is a possible topological order?
Show hintHide hint
Focus on the dependencies before drawing the order.
Question 6.
If a vertex D has an in-degree of 2 and is eliminated, how would that affect the graph?
Show hintHide hint
Think about how dependencies work.

5 more questions in this section. Enroll free to practise them all.