Assume that all the graphs in the fol- lowing problems are simple, with no self-loops or...

 

Transcribed Image Text:

Assume that all the graphs in the fol- lowing problems are simple, with no self-loops or multiple edges (in the same direction) between any two vertices. (a) Show that the total number of edges for a connected undirected graph with n vertices is bounded between n - 1 and (2), i.e., n-1≤m≤ (2) (b) Show that the total number of edges for a strongly connected directed graph with n vertices is bounded between n and n(n-1). (Hint: If we remove the directions, n - 1 suffices. Why having n - 1 edges isn't sufficient to ensure strong connectivity in a directed graph?) (c) Given a graph with n vertices and edge set E as the input, write the pseudocode of algorithms that achieve the following tasks: i. Assuming E is the adjacency linked list of undirected edges, given a vertex s, return the list of vertices that are reachable from s. This is called the connected component of s. ii. Let's refer to the function from the previous part as Connected Comp. Now, write an algo- rithm that returns the set of edges required to make your graph connected. The algorithm should also minimize the number of edges returned, and its time complexity should be O(m +n). Assume that all the graphs in the fol- lowing problems are simple, with no self-loops or multiple edges (in the same direction) between any two vertices. (a) Show that the total number of edges for a connected undirected graph with n vertices is bounded between n - 1 and (2), i.e., n-1≤m≤ (2) (b) Show that the total number of edges for a strongly connected directed graph with n vertices is bounded between n and n(n-1). (Hint: If we remove the directions, n - 1 suffices. Why having n - 1 edges isn't sufficient to ensure strong connectivity in a directed graph?) (c) Given a graph with n vertices and edge set E as the input, write the pseudocode of algorithms that achieve the following tasks: i. Assuming E is the adjacency linked list of undirected edges, given a vertex s, return the list of vertices that are reachable from s. This is called the connected component of s. ii. Let's refer to the function from the previous part as Connected Comp. Now, write an algo- rithm that returns the set of edges required to make your graph connected. The algorithm should also minimize the number of edges returned, and its time complexity should be O(m +n).

Answer rating: 100% (QA)

a i For a connected undirected graph with n vertices the minimum numb... View the full answer