Chapter 32 Flashcards
1
Q
How we get a cycle in graph
A
If there is a back edge (u, v) in tree, then v is an ancestor of u and by following tree edge from v to u, we get a cycle.
2
Q
What is precedence constraint graph
A
Precedence constraint graph is a DAG (directed acyclic graph) in which vertices are tasks and the edge (u, v) means that task u must be completed before task v begins. It describes the order of tasks to be done and precedence of them. For example construction of a building. First first floor, then second floor then 3rd floor
3
Q
What is topological order
A
The order of tasks according to their finish line and vertices in linear order.
4
Q
What is running time of topological sort order in DFS
A
theta (V+E)
