(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
- ka) Represent the given directed graphs(a) using an adjacency matrix. (b) Draw an undirected graph represented by the given adjacency matrix(b). а. b.arrow_forwardGiven the following adjacency matrix representation of a graph to answer the followed questions. 0 1 1 0 1 100 10 A.. B. I C. D.₁. 1000 1 0 0 1 0 0 1 0 1 1 is it directed graph or not and why? ] How many vertices are there in the graph? How many edges are there in the graph? reRepresent the graph using an adjacency list.arrow_forwardA set of vertices in a graph G = (V,E) is independent if no two of them are adjacent. Let G = (V,E) be an undirected graph with subset I of V an independent set. Let the degree of each vertex in V be at least 2. Also let |E| - E a ɛl deg(a) + 2 ||| < |V| Can G have a Hamiltonian cycle?arrow_forward
- A 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_forwardConsider this directed graph to the right: a) Now suppose the graph above is a residual graph after processing two augmenting paths. What were those paths and what were their flows? b) Draw the original directed acyclic graph and provide the maximum flow of this graph below. You may use either Ford-Fulkerson or Edmunds Karp to find the solution. Please show your workarrow_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_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_forwardQuestion No 4. Consider the following graph a. Find all the simple paths from node A to node E b. Find indeg(D) and outdeg(D) c. Are there any sources or sinks d. Find the adjacency matrix for the graph Darrow_forwardQUESTION 1: Given the following adjacency matrix representation of a graph to answer the followed questions. 01 1 0 0 0 0 1 1 1 0 1 |0 1 1 1 1 1 1 A. is it directed graph or not and why? B. How many vertices are there in the graph? C. How many edges are there in the graph? D. reRepresent the graph using an adjacency list. E. Draw the original grapharrow_forward
- a) Now suppose the graph above is a residual graph after processing two augmenting paths. What were those paths and what were their flows? b) Draw the original directed acyclic graph and provide the maximum flow of this graph below. You may use either Ford-Fulkerson or Edmunds Karp to find the solution. Please show your workarrow_forwardConsider the un-directed graph shown in the Fig. The values inside the node refer to the feature value of the node. The order of the nodes is A,B,C,D when following the matrix form in below questions.(You can use python or other languages to find the eigen values and other operationfor this question):1. For the given graph, write down the degree matrix, adjacency matrix, and Laplacian matrix representation.2.Find the eigenvalues and eigenvectors of the graph Laplacian matrix. Do you see any pattern pertaining to the signs of the eigenvalues (all positive or negative or no such pattern). Will it be same for all such graph Laplacianmatrices, and why?arrow_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_forward
- Database System ConceptsComputer ScienceISBN:9780078022159Author:Abraham Silberschatz Professor, Henry F. Korth, S. SudarshanPublisher:McGraw-Hill EducationStarting Out with Python (4th Edition)Computer ScienceISBN:9780134444321Author:Tony GaddisPublisher:PEARSONDigital Fundamentals (11th Edition)Computer ScienceISBN:9780132737968Author:Thomas L. FloydPublisher:PEARSON
- C How to Program (8th Edition)Computer ScienceISBN:9780133976892Author:Paul J. Deitel, Harvey DeitelPublisher:PEARSONDatabase Systems: Design, Implementation, & Manag...Computer ScienceISBN:9781337627900Author:Carlos Coronel, Steven MorrisPublisher:Cengage LearningProgrammable Logic ControllersComputer ScienceISBN:9780073373843Author:Frank D. PetruzellaPublisher:McGraw-Hill Education