In this question, we consider the operation of the Ford-Fulkerson algorithm on the network shown overleaf: 0/16 0/12 0/8 2/1 0/4 22 0/8 0/5 29 0/11 0/13 0/14 0/2 0/11 0/10 Each edge is annotated with the current flow (initially zero) and the edge's capacity. In general, a flow of x along an edge with capacity y is shown as x/y. (a) Show the residual graph that will be created from this network with the given (empty) flow. In drawing a residual graph, to show a forward edge with capacity and a backward edge with capacity y, annotate the original edge . (b) What is the bottleneck edge of the path (s. ₁, v. vs. t) in the residual graph you have given in answer to part (a)?

In this question, we consider the operation of the Ford-Fulkerson algorithm on the network shown overleaf: 0/16 0/12 0/8 2/1 0/4 22 0/8 0/5 29 0/11 0/13 0/14 0/2 0/11 0/10 Each edge is annotated with the current flow (initially zero) and the edge's capacity. In general, a flow of x along an edge with capacity y is shown as x/y. (a) Show the residual graph that will be created from this network with the given (empty) flow. In drawing a residual graph, to show a forward edge with capacity and a backward edge with capacity y, annotate the original edge . (b) What is the bottleneck edge of the path (s. ₁, v. vs. t) in the residual graph you have given in answer to part (a)?

Database System Concepts

7th Edition

ISBN:9780078022159

Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Publisher:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Chapter1: Introduction

Section: Chapter Questions

Problem 1PE

See similar textbooks

Similar questions

0/16 0/12 0/8 0/4 22 0/8 0/5 0/11 VA 0/13 0/14 V5 0/2 0/11 0/10 Each edge is annotated with the current flow (initially zero) and the edge's capacity. In general, a flow of x along an edge with capacity y is shown as x/y. (a) Show the residual graph that will be created from this network with the given (empty) flow. In drawing a residual graph, to show a forward edge with capacity x and a backward edge with capacity y, annotate the original edge *; y. (b) What is the bottleneck edge of the path (S, V₁, V3, V5, t) in the residual graph you have given in answer to part (a) ? (c) Show the network with the flow (s, V₁, V3, V5, t) that results from augmenting the flow based on the path of the residual graph you have given in answer to part (a). (d) Show the residual graph for the network flow given in answer to part (c). (e) What is the bottleneck edge of the path (s, v3, v4, t) in the residual graph you have given in answer to part (d) ?
One can manually count path lengths in a graph using adjacency matrices. Using the simple example below, produces the following adjacency matrix: A B A 1 1 B 1 0 This matrix means that given two vertices A and B in the graph above, there is a connection from A back to itself, and a two-way connection from A to B. To count the number of paths of length one, or direct connections in the graph, all one must do is count the number of 1s in the graph, three in this case, represented in letter notation as AA, AB, and BA. AA means that the connection starts and ends at A, AB means it starts at A and ends at B, and so on. However, counting the number of two-hop paths is a little more involved. The possibilities are AAA, ABA, and BAB, AAB, and BAA, making a total of five 2-hop paths. The 3-hop paths starting from A would be AAAA, AAAB, AABA, ABAA, and ABAB. Starting from B, the 3-hop paths are BAAA, BAAB, and BABA. Altogether, that would be eight 3-hop paths within this graph. Write a program…
Consider the following graph. We are finding the lengths of the shortest paths from vertex a to all vertices by the Relaxation algorithm from the lecture: At the beginning, every vertex v is set as unmarked and h(v) = +∞. Then a is set as open and h(a) = 0. How many ways there are to select five (at that moment) open vertices so that after their relaxation (and closing) the value of h(v) will represent the shortest path length from a to every v in the graph? Specify the number of ways and one such way separated by commas and spaces, for example 25, b, а, с, а, d. d 3 1 a 1 -4 -4
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.)
We are given a directed graph G = (V, E) with edge weights w(e) for e E E. The edge weights are allowed to be negative. Let -C be the minimum value of the edge weights. Create a new set of edge weights w'(e) = w(e) + C. Thus these new weights are non-negative: w'(e) ≥ 0 for all e € E. Run Dijkstra's algorithm from a specified start vertex s € V on G with these new weights w'. For every graph G, every weights w, and every s E V, the above algorithm is guaranteed to find the shortest paths in G (not the actual lengths but the paths) from s with respect to the original weights w: True O False If you entered true, provide a short explanation. If you entered false provide a counterexample (show the graph and what the algorithm produces vs. the correct solution).
We are given a directed graph G = (V, E) with edge weights w(e) for e E E. The edge weights are allowed to be negative. Let -C be the minimum value of the edge weights. Create a new set of edge weights w' (e) = w(e) + C. Thus these new weights are non-negative: w' (e) > 0 for all e € E. Run Dijkstra's algorithm from a specified start vertex s E V on G with these new weights w'. For every graph G, every weights w, and every s € V, the above algorithm is guaranteed to find the shortest paths in G (not the actual lengths but the paths) from s with respect to the original weights w: True False If you entered true, provide a short explanation. If you entered false provide a counterexample (show the graph and what the algorithm produces vs. the correct solution).
Given N cities represented as vertices V₁, V2, un on an undirected graph (i.e., each edge can be traversed in both directions). The graph is fully-connected where the edge eij connecting any two vertices vį and vj is the straight-line distance between these two cities. We want to search for the shortest path from v₁ (the source) to VN (the destination). ... Assume that all edges have different values, and €₁,7 has the largest value among the edges. That is, the source and destination have the largest straight-line distance. Compare the lists of explored vertices when we run the uniform-cost search and the A* search for this problem. Hint: The straight-line distance is the shortest path between any two cities. If you do not know how to start, try to run the algorithms by hand on some small cases first; but remember to make sure your graphs satisfy the conditions in the question.
the shortest path from S to C indeed has distance 7, and this path is S -> E -> D -> A -> C.
We recollect that Kruskal's Algorithm is used to find the minimum spanning tree in a weighted graph. Given a weighted undirected graph G = (V , E, W), with n vertices/nodes, the algorithm will first sort the edges in E according to their weights. It will then select (n-1) edges with smallest weights that do not form a cycle. (A cycle in a graph is a path along the edges of a graph that starts at a node and ends at the same node after visiting at least one other node and not traversing any of the edges more than once.) Use Kruskal's Algorithm to nd the weight of the minimum spanning tree for the following graph.
The major problem with the electric cars is the battery capacity. The batteries used in these cars are generally very heavy and expensive, so engineers must make important trade-offs when determining the battery capacity, and therefore the range, of these vehicles. Suppose that the road network is defined by an undirected weighted graph G = (V, E). The vertices represent the cities, the edges represent the distance between the two cities, and the weight represents the distance between two cities. Assume that each city has EV charger stations so that the driver can charge the car's battery. Write an O (E| log |E|) algorithm to determine the minimum range of the car that enables it to drive from every city to every other city.
Consider a graph with five nodes labeled A, B, C, D, and E. Let's say we have the following edges with their weights: A to B with weight 3 A to C with weight 1 B to C with weight 2 B to D with weight 1 C to E with weight 4 D to E with weight 2 a. Find the shortest path from A to E using Dijkstra's algorithm b. Use Prim to find the MST c. Use Kruskal to find the MST d. What's the difference between Prim and Kruskal algorithms? Do they always have the same result? Why or why not.
The given inputs consist of two nodes (s, t) and a directed graph G = (V, E). In addition, each edge of the graph is either blue or red. The goal is to find a path from point s to point t such that red edges always follow blue edges. There need not be any red or blue borders on the route, but if there are, the red ones should follow the blue ones. Develop an algorithm that does the task in O(n + m) time and analyze its performance.