1. 18 pts): Consider the following directed graph Part A [4 pts]: Work out the f

Question

1. 18 pts): Consider the following directed graph Part A [4 pts]: Work out the flows along each edge that give the maximum flow for this graph, and then on the lines below, enter the flow on each link in your solution. There are multiple solutions, you only need one. Solution Part B [2 pts]: A bottleneck edge in a flow graph is an edge such that if you increase the capacity of that edge you can increase the maximum flow through the network without increasing the capacity of any other edge. Are there any bottleneck edges in the graph? If so, which are they? Solution Part C [2 pts]: If you think there is at least one bottleneck edge, increase the capacity of one bottleneck edge by one unit. List a path (a sequence of nodes) that you could follow to augment the flow from source S to sink T by one unit. Be sure that your augmentation is consistent with the flow network you created for part A. If you think there are no bottleneck edges, and you are correct, leave this blank for two points Solution

Explanation / Answer

part A:  

A->D : 3

B->A : 3

B->C : 2

B->E : 3

C->A : 2

C->D : 2

C->E : 3

D->E : 2

D->T : 5

E->T : 5

S->A : 4

S->B : 3

S->D : 2

There is no bottle neck edge is availabe to get the maximum output

Related Questions

Navigate

• Browse (All)
• Browse 1
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.