We will look at how the Ford-Fulkerson Algorithm operates on the following network.
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 x ; y.
[4 marks]
(b) What is the bottleneck edge of the path (s, v1, v3, v5, t) in the residual graph you have given in answer to Question 3a?
[2 marks]
(c) Show the network with the flow that results from augmenting the flow based on the path (s, v1, v3, v5, t) of the residual graph you have given in answer to Question 3 a.
[3 marks]
(d) Show the residual graph for the network flow given in answer to Question 3c.
[4 marks]
(e) What is the bottleneck edge of the path (s, v3, v4, t) in the residual graph you have given in answer to Question 3 d ?
[2 marks]
(f) Show the network with the flow that results from augmenting the flow based on the path (s, v3, v4, t) of the residual graph you have given in answer to Question 3 d.
[3 marks] Question 3 f.
[4 marks]
h) What is the bottleneck edge of the path (s, v2, v3, v1, v4, t) in the residual graph you have given in answer to Question 3 g ?
[2 marks]
(i) Show the network with the flow that results from augmenting the flow based on the path (s, v2, v3, v1, v4, t) of the residual graph you have given in answer to Question 3 g.
[3 marks]
(j) Show the residual graph for the network flow given in answer to Question 3 i.
[4 marks]
(k) Show the final flow that the Ford-Fulkerson Algorithm finds for this network, given that it proceeds to completion from the flow rates you have given in answer to Question 3i, and augments flow along the edges (s, v1, v3, t) and (s, v2, v5, t)
[4 marks]
(l) Identify a cut of the network that has a cut capacity equal to the maximum flow of the network.
[5 marks]
\
Homework Answers
Add Answer to:
We will look at how the Ford-Fulkerson Algorithm operates on the following network.
03:25 pts) For the edge weight matrix assigned to you for a directed graph, determine the...
03:25 pts) For the edge weight matrix assigned to you for a directed graph, determine the shortest path weights between any two vertices of the graph using the Floyd-Warshall algorithm. Show clearly the distance matrix and the predecessor matrix for each iteration Also, extract a path of length two or above between any two vertices of your choice. Clearly show the path extraction steps, as shown in the slides. V1 V1 9 V2 0 V3 3 w 85 V2 V3...
QUESTION 1 Let V-L2([0,1 ],C) and > : Vx-СУч . Г f(x)g(x)dx be an inner product...
QUESTION 1 Let V-L2([0,1 ],C) and > : Vx-СУч . Г f(x)g(x)dx be an inner product on V Let gor 91, 92, 93:0,1]R be given by gox)-1,g1(x)-x, 920x)-x2, g3(x) -x3 and consider the following subset S = { go, g 1, g 2, g3JC V. After applying the Gram-Schmidt process the following set of vectors T = {vo, vľ, V2, V3} is an orthonormal set, where V1, V2, V3, and V4 are given by: O vo= 1, v,-V3(2x-1), v,-V5 (6x2-6x...
Say that we have an undirected graph G(V, E) and a pair of vertices s, t and a vertex v that we call a a desired middle vertex . We wish to find out if there exists a simple path (every vertex appears...
Say that we have an undirected graph G(V, E) and a pair of vertices s, t and a vertex v that we call a a desired middle vertex . We wish to find out if there exists a simple path (every vertex appears at most once) from s to t that goes via v. Create a flow network by making v a source. Add a new vertex Z as a sink. Join s, t with two directed edges of capacity...
Please answer A and B 1. Consider the following adjacency matrix representing vertices v through v^:...
Please answer A and B
1. Consider the following adjacency matrix representing vertices v through v^: weighted graph containing a ro 5 0 0 8 0 61 5 0 0 7 0 0 0 jo 0 0 0 0 1 3| 0 7 0 0 2 0 0 8 0 0 0 0 1 0 0 0 4 L6 0 3 0 0 4 0- 20 0 0 a. Draw the graph resulting from the adjacency matrix b. Assuming the...
1. Linear programming can be used to calculate the maximum flow in a network from the...
1. Linear programming can be used to calculate the maximum flow in a network from the source s, to the sink t. Which of the following statements below gives the correct objective function, and number of constraints for applying a linear program for computing maximum flow in the following graph? In this graph, the maximum capacity of each edge is given as the number next to the corresponding edge. The flow along an edge eſi, j) is denoted by fij....
I posted it twice a day. One gave me a code while the question is not...
I posted it twice a day. One gave me a code while the question
is not asking about code and is asking to give a graph solution and
the other gave a wrong answer for the graph.
Is anyone knowledgeable of this topic and can answer this
question?
PLEASE, don't give me a code for irrelevant
question.
3. The following flow graph G has some flow assignments already made. Use the Ford-Fulkersoin method to continue the process of deriving the...
5 Network Flow, 90p. Consider the below flow network, with s the source and t the sink. 5 4 1. (10p) Draw a flow with value 8. (You may write it on top of the edges in the graph above, or draw a...
5 Network Flow, 90p. Consider the below flow network, with s the source and t the sink. 5 4 1. (10p) Draw a flow with value 8. (You may write it on top of the edges in the graph above, or draw a new graph.) You are not required to show how you construct the flow (though it may help you to apply say the Edmonds-Karp algorithm). 2. (5p) List a cut with capacity 8. (You may draw it in...
1. (25) [Maximum bottleneck rate spanning treel] Textbook Exercise 19 in Chapter 4. Given a connected...
1. (25) [Maximum bottleneck rate spanning treel] Textbook Exercise 19 in Chapter 4. Given a connected graph, the problem is to find a spanning tree in which every pair of nodes has a maximum bottleneck rate path between the pair. (Note that the bottleneck rate of a path is defined as the minimum bandwidth of any edge on the path.) First give the algorithm (a sketch of the idea would be sufficient), and then prove the optimality of the algorithm....
Can u please answer the question (G) 1. (15 marks total) Consider the real vector space (IR3, +,-) and let W be the sub...
Can u please answer the question (G)
1. (15 marks total) Consider the real vector space (IR3, +,-) and let W be the subset of R3 consisting of all elements (z, y, z) of R3 for which z t y-z = 0. (Although you do not need to show this, W is a vector subspace of R3, and therefore is itsclf a rcal vector space.) Consider the following vectors in W V2 (0,2,2) V (0,0,0) (a) (2 marks) Determine whether...
A survey of a random sample of 400 Telfer undergraduate students in third or fourth year...
A survey of a random sample of 400 Telfer undergraduate students in third or fourth year was carried out to gather information for research about student life. Questions were asked about demographic characteristics, grades, study habits, and leisure activities. Here are some of the variables for which data were collected (they are labeled V1 through V9. for convenience). Assume that quantitative variables are normally distributed • V1: First-year overall grade (percent) • V2: Gender (1 male, 2-female) • V3: Opinion...
03:25 pts) For the edge weight matrix assigned to you for a directed graph, determine the shortest path weights between any two vertices of the graph using the Floyd-Warshall algorithm. Show clearly the distance matrix and the predecessor matrix for each iteration Also, extract a path of length two or above between any two vertices of your choice. Clearly show the path extraction steps, as shown in the slides. V1 V1 9 V2 0 V3 3 w 85 V2 V3...
QUESTION 1 Let V-L2([0,1 ],C) and > : Vx-СУч . Г f(x)g(x)dx be an inner product on V Let gor 91, 92, 93:0,1]R be given by gox)-1,g1(x)-x, 920x)-x2, g3(x) -x3 and consider the following subset S = { go, g 1, g 2, g3JC V. After applying the Gram-Schmidt process the following set of vectors T = {vo, vľ, V2, V3} is an orthonormal set, where V1, V2, V3, and V4 are given by: O vo= 1, v,-V3(2x-1), v,-V5 (6x2-6x...
Please answer A and B
1. Consider the following adjacency matrix representing vertices v through v^: weighted graph containing a ro 5 0 0 8 0 61 5 0 0 7 0 0 0 jo 0 0 0 0 1 3| 0 7 0 0 2 0 0 8 0 0 0 0 1 0 0 0 4 L6 0 3 0 0 4 0- 20 0 0 a. Draw the graph resulting from the adjacency matrix b. Assuming the...
1. Linear programming can be used to calculate the maximum flow in a network from the source s, to the sink t. Which of the following statements below gives the correct objective function, and number of constraints for applying a linear program for computing maximum flow in the following graph? In this graph, the maximum capacity of each edge is given as the number next to the corresponding edge. The flow along an edge eſi, j) is denoted by fij....
I posted it twice a day. One gave me a code while the question
is not asking about code and is asking to give a graph solution and
the other gave a wrong answer for the graph.
Is anyone knowledgeable of this topic and can answer this
question?
PLEASE, don't give me a code for irrelevant
question.
3. The following flow graph G has some flow assignments already made. Use the Ford-Fulkersoin method to continue the process of deriving the...
5 Network Flow, 90p. Consider the below flow network, with s the source and t the sink. 5 4 1. (10p) Draw a flow with value 8. (You may write it on top of the edges in the graph above, or draw a new graph.) You are not required to show how you construct the flow (though it may help you to apply say the Edmonds-Karp algorithm). 2. (5p) List a cut with capacity 8. (You may draw it in...
1. (25) [Maximum bottleneck rate spanning treel] Textbook Exercise 19 in Chapter 4. Given a connected graph, the problem is to find a spanning tree in which every pair of nodes has a maximum bottleneck rate path between the pair. (Note that the bottleneck rate of a path is defined as the minimum bandwidth of any edge on the path.) First give the algorithm (a sketch of the idea would be sufficient), and then prove the optimality of the algorithm....
Can u please answer the question (G)
1. (15 marks total) Consider the real vector space (IR3, +,-) and let W be the subset of R3 consisting of all elements (z, y, z) of R3 for which z t y-z = 0. (Although you do not need to show this, W is a vector subspace of R3, and therefore is itsclf a rcal vector space.) Consider the following vectors in W V2 (0,2,2) V (0,0,0) (a) (2 marks) Determine whether...
A survey of a random sample of 400 Telfer undergraduate students in third or fourth year was carried out to gather information for research about student life. Questions were asked about demographic characteristics, grades, study habits, and leisure activities. Here are some of the variables for which data were collected (they are labeled V1 through V9. for convenience). Assume that quantitative variables are normally distributed • V1: First-year overall grade (percent) • V2: Gender (1 male, 2-female) • V3: Opinion...
Most questions answered within 3 hours.
-
Propose an efficient synthesis of 2-Bromo-5-nitrotoluene from
benzene. Hint: 3 steps. Consider directing effects of substituents....
asked 2 hours ago -
Name the following coordination compounds using systematic
nomenclature.
1. [Co(H2O)6]Cl2:
2. [Cr(NH3)6](NO3)3:
3. K4[Fe(CN)6]:
4. Na[Au(CN)4]:...
asked 46 minutes ago -
This assignment will explore the impact of corporate decisions
on a local versus a global perspective....
asked 1 hour ago -
Given the function below, F(w,x,y,z)= x’z+w’z’+w’y
a) draw a logic diagram for an implementation which uses...
asked 1 hour ago -
The sandwich maker of the EE-Cole-Eye Sandwich Truck was just
fired (for a reason described below)...
asked 1 hour ago -
Most political philosophers believe we have a duty to obey laws,
even if the laws in...
asked 2 hours ago -
Which of the following are common negotiation outcome
mistakes?
a. Leave money on the table b....
asked 2 hours ago -
Convert the following quantities:
a) 0.819 atm to torr b) 512 mmHg to bar c) 11.2...
asked 3 hours ago -
C ++ Implement cat command
The purpose of this assignment is to provide practice using the...
asked 3 hours ago -
we
convert sugars into another form of stored potential energy. This
is called?
asked 4 hours ago -
The manufacturers of Oriental Spice Sauce are concerned that the
sodium levels in their product vary...
asked 4 hours ago -
PLEASE DON'T ANSWER IF YOU CAN'T ANSWER ALL OF THE QUESTIONS. I
DESPERATELY NEED HELP
Consider...
asked 4 hours ago