A digraph G = (V,E) is called a one-way connected graph if for every two vertices...

  

Transcribed Image Text:

A digraph G = (V,E) is called a one-way connected graph if for every two vertices u, v V, either there is a path from u to v or there is a path from v to u (but never both, so u and v can never be strongly connected). a. (6 marks) State a necessary and sufficient condition for a digraph to be one-way connected. Prove its correctness (i.e., prove it is a necessary condition and also a sufficient condition). Note: Here is an incorrect answer. Consider the condition "every pair of vertices u and v are not strongly connected". It is obviously a necessary condition, since a one-way connected graph cannot have both a path from u to v and a path from v to u. While it is NOT a sufficient condition, since a digraph satisfying this condition may not be a one-way connected graph (e.g.: In a digraph with three vertices 1, 2, 3 and two edges (1, 2) and (3,2), each pair of vertices are not strongly connected, and the digraph is also not one-way connected since there is no path between 1 and 3). b. (5 marks) Describe an efficient algorithm to determine whether or not an input digraph G = (V,E) is one-way connected. Analyze the running time of your algorithm. (Hint: Make use of the condition you state in part a.) A digraph G = (V,E) is called a one-way connected graph if for every two vertices u, v V, either there is a path from u to v or there is a path from v to u (but never both, so u and v can never be strongly connected). a. (6 marks) State a necessary and sufficient condition for a digraph to be one-way connected. Prove its correctness (i.e., prove it is a necessary condition and also a sufficient condition). Note: Here is an incorrect answer. Consider the condition "every pair of vertices u and v are not strongly connected". It is obviously a necessary condition, since a one-way connected graph cannot have both a path from u to v and a path from v to u. While it is NOT a sufficient condition, since a digraph satisfying this condition may not be a one-way connected graph (e.g.: In a digraph with three vertices 1, 2, 3 and two edges (1, 2) and (3,2), each pair of vertices are not strongly connected, and the digraph is also not one-way connected since there is no path between 1 and 3). b. (5 marks) Describe an efficient algorithm to determine whether or not an input digraph G = (V,E) is one-way connected. Analyze the running time of your algorithm. (Hint: Make use of the condition you state in part a.)