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