

Chegg Guided Solutions for Algorithms 1st Edition Chapter 3 Problem 13

0 Stars(0 users)

Undirected vs. directed connectivity.

(a) Prove that in any connected undirected graph G = (V, E) there is a vertex v ϵ V whose removal 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 every v ϵ 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 graph connected by adding only one edge. Give an example of a directed graph with two strongly connected components such that no addition of one edge can make the graph strongly connected.

    View this solution... try Chegg Study


    Join now