Solution Found!
Undirected vs. directed connectivity.(a) Prove that in any connected undirected graph G
Chapter 3, Problem 3.13(choose chapter or problem)
Undirected vs. directed connectivity.(a) Prove that in any connected undirected graph G = (V, E) there is a vertex v V whoseremoval leaves G connected. (Hint: Consider the DFS search tree for G.)(b) Give an example of a strongly connected directed graph G = (V, E) such that, for everyv V , removing v from G leaves a directed graph that is not strongly connected.(c) In an undirected graph with 2 connected components it is always possible to make the graphconnected by adding only one edge. Give an example of a directed graph with two stronglyconnected components such that no addition of one edge can make the graph strongly connected.
Questions & Answers
QUESTION:
Undirected vs. directed connectivity.(a) Prove that in any connected undirected graph G = (V, E) there is a vertex v V whoseremoval leaves G connected. (Hint: Consider the DFS search tree for G.)(b) Give an example of a strongly connected directed graph G = (V, E) such that, for everyv V , removing v from G leaves a directed graph that is not strongly connected.(c) In an undirected graph with 2 connected components it is always possible to make the graphconnected by adding only one edge. Give an example of a directed graph with two stronglyconnected components such that no addition of one edge can make the graph strongly connected.
ANSWER:Step 1 of 4
If two vertices in a graph are connected to each other, that is there is a path from one vertex to the other and vice versa. This connected component partition is called strongly connected components of the graph. The connected components of the graph form the strongly connected graph. The directed acyclic graph is made with strongly connected components.