Data-Structures
November 13, 2023Algorithms
November 13, 2023Data-Structures
| Question 6 |
Which of the following is/are correct about the graph?
| For each pair of vertices u and v, there is a directed path from u to v. | |
| The graph does not have a strongly connected component. | |
| The graph does not have a topological order. | |
| A depth-first traversal staring at vertex S classifies three directed edges as back edges. |
Option-1: FALSE: There is no path from top right corner vertex to any other vertex
Option-2: FALSE: A directed graph is called strongly connected if there is a path in each direction between each pair of vertices of the graph. As there is no path from the above vertex then this statement is wrong.
Option-3: TRUE: This graph does have directed cycles, thus topological order can not be possible for according to topological definition.
Option-1: FALSE: There is no path from top right corner vertex to any other vertex
Option-2: FALSE: A directed graph is called strongly connected if there is a path in each direction between each pair of vertices of the graph. As there is no path from the above vertex then this statement is wrong.
Option-3: TRUE: This graph does have directed cycles, thus topological order can not be possible for according to topological definition.