(a)
To show that the updation procedure of transitive closer G * ( V , E *) of graph G ( V, E ) will take O ( V2 ) time, while an edge is added to the graph G .
(a)
Explanation of Solution
Here, in the graph G , if the updation of transitive closure takes O ( V2 ) time. To understand this scenario, suppose, addition of an edge ( x1 , x2 ) is performed in the graph G . Now, take the set of vertices ( u, v ) in order to get the path from u to x1 and x2 to v . If there is a possibility of having an edge that contains vertices in such manner like ( u , x1 ) and ( x2 , v ).
Therefore, perform addition of an edge ( u, v ) in transitive closure only if the closure holds the edges in ( u, x1 ) and ( x2, v ) manner. So, the consideration of pair required only once and the total run time of this procedure will be O ( V2 ).
(b)
To give an example that the update of transitive closer will take O ( V2 ) time, when a new edge ‘ e’ is added to the graph G .
(b)
Explanation of Solution
Consider the condition where there aretwo strongly connected components with sizes | V |/2 and there is no common edge between them. The transitive closure can be computed by adding these two connected components of the graph.
Now, perform addition of a single edge between two connected components that provide connectivity between two separate components of the graph. Here, it is clearly visible that the total no. of edges will be increased by | V |/4 and the total no of edges will be [| V |/2 + | V |/4]. So, every time while adding a new edge required a constant time at least.
Therefore, the update of transitive closer will take O ( V2 ) time, when a new edge ‘ e’ is added to the graph G .
(c)
To define an
(c)
Explanation of Solution
Consider a set of vertices in the graphG , and there is a path between every pair of vertices. Now, while performing an addition of an edge ( u, v ), look at the ancestor of vertex u and add it there. The reason of looking at the ancestor of an edge is to explore the branches of the tree. This procedure will also applicable for the vertex v. through this, it will be very easy to get the already added edges and will only consider those edges in n times mostly.
Since, the edges in the tree required O ( V2 ) time for consideration. Therefore, the total time taken by the algorithm will be O ( V3 ).
Want to see more full solutions like this?
Chapter 25 Solutions
Introduction to Algorithms
- please explain fullyarrow_forwardA Hamiltonian path on a directed graph G = (V, E) is a path that visits each vertex in V exactly once. Consider the following variants on Hamiltonian path: (a) Give a polynomial-time algorithm to determine whether a directed graph G contains either a cycle or a Hamiltonian path (or both). Given a directed graph G, your algorithm should return true when a cycle or a Hamiltonian path or both and returns false otherwise. (b) Show that it is NP-hard to decide whether a directed graph G’ contains both a cycle and a Hamiltonian Path, by giving a reduction from the HAMILTONIAN PATH problem: given a graph G, decide whether it has a Hamiltonian path. (Recall that the HAMILTONIAN PATH problem is NP-complete.)arrow_forward........arrow_forward
- For a directed graph G = (V,E) (source and sink in V denoted by s and t respec- tively) with capacities c: E→+, and a flow f: E→, the support of the flow f on G is the set of edges E:= {e E| f(e) > 0}, i.e. the edges on which the flow function is positive. Show that for any directed graph G = (V,E) with non-negative capacities e: Ethere always exists a maximum flow f*: E→+ whose support has no directed cycle.arrow_forwardWe are given a graph G = (V, E); G could be a directed graph or undirected graph. Let M bethe adjacency matrix of G. Let n be the number of vertices so that the matrix M is n ×n matrix. For anymatrix A, let us denote the element of i-th row and j-th column of the matrix A by A[i, j].1. Consider the square of the adjacency matrix M . For all i and j, show that M 2[i, j] is the number ofdifferent paths of length 2 from the i-th vertex to the j-th vertex. It should be explained or proved asclearly as possible.2. For any positive integer k, show that M k[i, j] is the number of different paths of length k from the i-th vertex to the j-th vertex. You may use induction on k to prove it.3. Assume that we are given a positive integer k. Design an algorithm to find the number of different paths of length k from the i-th vertex to j-th vertex for all pairs of (i, j). The time complexity of your algorithm should be O(n3 log k). You can get partial credits if you design an algorithm of O(n3k).arrow_forward4. Graphs represented in Matrixarrow_forward
- 4. Graphs represented in Adjacency Matricesarrow_forwardAdvanced Physics Chegg experts gave the wrong answer the last time I asked this, so I am asking it again. Please only answer if you know how to solve the problem! Consider a directed graph G = (V, E) having a source vertex s and sink vertex t. Suppose that it has positive integer edge capacities c_e for all edges in the graph. Also suppose that is has a flow f = {f(e)} for all edges in the graph. We consider an edge to be saturated if f(e) = c_e. Suppose that f is a maximum s-t flow. Let S represent the set of all saturated edges. Consider the minimum total capacity of any given s-t cut. Will it be equal to the total capacity of S? If true, please provide a proof. Otherwise, if it is false, give a counterexample.arrow_forwardQUESTION 1: Given the following adjacency matrix representation of a graph to answer the followed questions. 0 11|0| 1 1001| 0 01 0 0 0100 | 1 1 1 | 0 1 1 D. reRepresent the graph using an adjacency list. E. Draw the original grapharrow_forward
- Consider a directed graph G = (V, E), and two distinct vertices u, v V. Recall that a set of U-V paths is non-overlapping if they have no edges in common among them, and a set C of edges disconnects from U if in the graph (V, E-C) there is no path from U to V. Suppose we want to show that for any set of non-overlapping paths P and any disconnecting set C, |P| ≤ |C|. Consider the proof that defines A = P, B = C and f(path q) = qC, and applies the Pigeonhole Principle to obtain the result. True or False: f is a well-defined function (i.e. it satisfies the 3 properties of a well- defined function). True Falsearrow_forwardTrue or False Let (u, v) be an edge in a maximum flow graph with capacity greater than 0.Then it is possible that the residual graph contains (v, u), but not (u, v).arrow_forwardPlease help with this question:arrow_forward
Database System ConceptsComputer ScienceISBN:9780078022159Author:Abraham Silberschatz Professor, Henry F. Korth, S. SudarshanPublisher:McGraw-Hill Education
Starting Out with Python (4th Edition)Computer ScienceISBN:9780134444321Author:Tony GaddisPublisher:PEARSON
Digital Fundamentals (11th Edition)Computer ScienceISBN:9780132737968Author:Thomas L. FloydPublisher:PEARSON
C How to Program (8th Edition)Computer ScienceISBN:9780133976892Author:Paul J. Deitel, Harvey DeitelPublisher:PEARSON
Database Systems: Design, Implementation, & Manag...Computer ScienceISBN:9781337627900Author:Carlos Coronel, Steven MorrisPublisher:Cengage Learning
Programmable Logic ControllersComputer ScienceISBN:9780073373843Author:Frank D. PetruzellaPublisher:McGraw-Hill Education