Programming: Check if graph is semiconnected
A directed graph G=(V,E) is semiconnected if, for all pairs of vertices (u,v)
we have u to v or v to u. Give an efficient algorithm to determine whether
or not G is semiconnected. Prove that your algorithm is correct, and analyze its
running time.
Call STRONGLY-CONNECTED-COMPONENTS.
Form the component graph.
Topologically sort the component graph. It is possible to topologically sort the component graph, because component graph is always a DAG (Directed Acyclic Graph)
Verify that the sequence of vertices (v1,v2,...vk) given by topological sort forms a linear chain in the component graph. That is, verify that the edges (v1,v2),(v2,v3) ,(v (k-1),vk) exist in the component graph. If the vertices form a linear chain, then the original graph is semiconnected; otherwise it is not.
we have u to v or v to u. Give an efficient algorithm to determine whether
or not G is semiconnected. Prove that your algorithm is correct, and analyze its
running time.
Call STRONGLY-CONNECTED-COMPONENTS.
Form the component graph.
Topologically sort the component graph. It is possible to topologically sort the component graph, because component graph is always a DAG (Directed Acyclic Graph)
Verify that the sequence of vertices (v1,v2,...vk) given by topological sort forms a linear chain in the component graph. That is, verify that the edges (v1,v2),(v2,v3) ,(v (k-1),vk) exist in the component graph. If the vertices form a linear chain, then the original graph is semiconnected; otherwise it is not.
Because we know that all vertices in each SCC are mutually reachable from each other, it suffices to show that the component graph is semiconnected if and only if it contains a linear chain.
Total running time is O(V+E).
Read full article from Programming: Check if graph is semiconnected
No comments:
Post a Comment