The Semi-Connectivity Problem: Given a digraph G = (V,E), determine whether or not G is semi-connected. G is semi-connected if and only if for every pair of its vertices u and v there is either a directed path from u to v or a directed path from v to u (or both). Below we investigate an efficient solution to this problem by using the Strongly Connected Components (SCC) algorithm.

a} Highlight the strongly connected components of digraph G below, and draw its SCC Component DAG on the right hand side. Is G semi-connected? Why?

b) State and prove a necessary and sufficient condition for the semi-connectivity of any digraph G expressed as a structural property of its SCC Component DAG.

c) Describe and analyze an efficient algorithm to solve the Semi-Connectivity Problem.

a e 6---d h-111 ! c b 1111111 f *1