Answered step by step
Verified Expert Solution
Question
1 Approved Answer
Suppose we start with a rooted tree, and add a direction to every edge, so that it points from parent to child. So, the root
Suppose we start with a rooted tree, and add a direction to every edge, so that it points from parent to child. So, the root has no edges going into it, and a leaf has no edges going out of it. Then for this directed graph that we have created: The graph will always uniquely determine a topological ordering The number of edges will be smaller than that in the original tree There will never be a directed cycle There will always be a directed path from any vertex to any other. QUESTION 19 A strongly connected graph is a directed graph where for any vertices u, v there is a directed path from u to v. Then: A directed acyclic graph is always strongly connected We can always define a topological ordering on a strongly connected graph A strongly connected graph with more than one vertex will never by acyclic. If a graph is not strongly connected then we cannot define a topological ordering. QUESTION 20 If there is a directed path from u to v and from v to w then: There will be a directed path from u to w, but it might not go through v There will be a directed path from u to u, and it will always go through v There will be a cycle in the graph which goes through u and w There will be a cycle in the graph but it might not go through u or w
Step by Step Solution
There are 3 Steps involved in it
Step: 1
Get Instant Access to Expert-Tailored Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started