(a) When do we say that undirected graph is connected, biconnected? When do we s
ID: 3919328 • Letter: #
Question
(a) When do we say that undirected graph is connected, biconnected? When do we say that a directed graph is strongly connected? Give definitions of a separation vertex, a separation edge. Demonstrate all(above) notions on examples of graphs.
(b) Describe (in pseudo-code) and explain an O(n+m) time algorithm that tests whether a directed graph G with n vertices and m edges is strongly connected. For this problem you are not allowed to assume the existence of any "black-box" algorithms - give pseudo-code for everything you use.
(c) Analyze the worst-case running time of your algorithm. Explain.
Explanation / Answer
(a)
Separation vertex: If removal of a vertex results in two different connected components then it's a separation vertex.
Separation edge: If the removal of an edge results in two different connected components then it's a separation edge.
(b) We will be using an algorithm named Kosaraju’s DFS based algorithm.
Time complexity is O(n+m). As we need two traversals of the whole graph.
3.)
As there are only two traversals required Best, Average and Worst case complexity is the same O(m+n). (I case of a complete graph where all nodes connected to all, the number of edges is m = n*n so O(m+n)=O(n^2)).
Thank you.
Plase Rate if you like my efforts. If you have any doubt or find any problem I am available in comments.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.