Consider the following network. Treat the rst number assigned to each edge as a
ID: 3801991 • Letter: C
Question
Consider the following network.
Treat the rst number assigned to each edge as a capacity and let the edges be directed by alphabetical order of their endpoints with L preceding a and W following n [e.g., the edge between f and i goesfrom f to i].
(a) If we say that the second number is the ow through the edge, is this a feasible L W ow?
(b) Find the maximum L W ow and a minimum L W cut in this network.
(c) By inspection, nd a dierent maximum L W ow.
(d) In addition, let the second number of each edge be a lower bound on the ow in that edge. Try to nd an L W ow satisfying both constraints.
8, 4 8, 5 3, 1 /5, 1 7, 2 4, 1 7, 2 5, 1 5, 2 4, 1 8, 3 4, 2 6, 3 7, 2 8, 4 12, 4. 6, 3 4, 2 4, 2 5, 3 8, 3 5, l 5, 5 m 6, 2Explanation / Answer
Solution A:- In the given network diagram shows that the each node of a network is to connected to each other. In this network the node are define through the direct communication between the each node so this is define the directed acyclic graph. In this network each node is labeled with the alphabetical order, the direct edge is connected the node of network.
Starting node is L and final node is W, we start the traversing from node (L) with weight capacity 1 and reaches node (a), we found the two node connected that is node c with weight 1 and b with weight 2, at node b there is two node (d,h) also connected to each after picking node(h), again traversing through node (h) to (j) with weight capacity 3 and found path node j to m, At node m to two directed node is connected to each other’s node( k) and (w )with weight 2 and reached final node( w) with the minimum path traversing to complete the final destination.
Now the conclusion is that we choose the shortest path between the each node is the network and final reaches the destination with minimum path traversing. The path is feasible between the nodes (L) to node (w) in the network.
Solution (B):-
Source node (L) and final node (W)
Minimum L-W cut: {(L,B),(b,h),(h,j),(j,m),(m,w))
Minimum Weight capacity: 8+7+6+5+6=32
Maximum L-W cut : {(L,a),(a,c),(c,e),(g,k),(k,i),(i,l),(l,w)
Maximum Weight capacity: 5+4+8+8+6+3+12+8=54
Solution(c):-
Different Maximum L-W cut:{(L,a),(a,b),(b,h),(h,f),(f,g),(g,i),(i,l),(l,w)
Maximum weight capacity: 5+5+7+4+3+4+12+8=48
Solution (d):- In each of node in the network having weight assigned to it. First for upper bound and second for lower bound. When we are start traversing from first node to traverse the next connected node then it means the we traverse the maximum and minimum weight capacity to it if we traverse the starting to final node in network and final to starting node than both the upper and lower bound of weight satisfying the condition with each other’s.