# Question

Suppose that we wish to maintain the transitive closure of a directed graph G = (V, E) as we insert edges into E. That is, after each edge has been inserted, we want to update the transitive closure of the edges inserted so far. Assume that the graph G has no edges initially and that the transitive closure is to be represented as a Boolean matrix.

a. Show how the transitive closure G* = (V, E*) of a graph G = (V, E) can be updated in O (V2) time when a new edge is added to G.

a. Show how the transitive closure G* = (V, E*) of a graph G = (V, E) can be updated in O (V2) time when a new edge is added to G.

## Answer to relevant Questions

Given a flow network G = (V, E), let f1 and f2 be functions from V × V to R. The flow sum f1 + f2 is the function from V × V to R defined by (26.4) (fi + f2) (u, v) = f1 (u, v) + f2(u, v) for all u, v ¬ V. If f1 ...Suppose that a flow network G = (V, E) has symmetric edges, that is, (u, v) ¬ E if and only if (v, u) ¬ E. Show that the Edmonds-Karp algorithm terminates after at most |V| |E|/4 iterations.Let G = (V, E) be a flow network with source s, sink t, and an integer capacity c (u, v) on each edge (u, v) ¬ E. Let C = max (u, v) Ec (u, v). a. Argue that a minimum cut of G has capacity at most C ...Give an example of a directed graph G = (V, E), a source vertex s ¬ V, and a set of tree edges E π ¬ E such that for each vertex v ¬ V, the unique path in the graph (V, E π) from s to v is a shortest path in G, ...Give an O (V + E)-time algorithm to compute the component graph of a directed graph G = (V, E). Make sure that there is at most one edge between two vertices in the component graph your algorithm produces.Post your question

0