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.