Consider the input of the Minimum-Congestion Multicommodity-Flow problem given by the following flow network with edge c

[answerhappygod]

Consider The Input Of The Minimum Congestion Multicommodity Flow Problem Given By The Following Flow Network With Edge C 1 (114.28 KiB) Viewed 15 times

Consider the input of the Minimum-Congestion Multicommodity-Flow problem given by the following flow network with edge capacities and the specification of three commodities. source destination amount Y z 4.0 7.5 8 /5 2 commodity 1 commodity 2 commodity 3 X Y 5.5 10 b с 8 3.0 (a) 12 8 1 10 The table below shows the flows of commodities 1 and 2. The flow of commodity 3 has not been decided yet. (The empty entries in the table indicate zero units of flow.) edge(a,y) (b.a) (b,x) (b,z) (c.a) (c,x) (x,y) (x,z) (y.b) (y,c) (z,c) commodity 1 2 3 2 5 commodity 2 2.5 2.5 3 2.5 2.5 commodity 3 Complete the following sentences by dragging and dropping the correct options. We decide to split the flow of commodity 3 equally between paths (b, z, c) and (b, x, y, c). With this flow of commodity 3, the maximum edge congestion of the combined flow (of all three commodities) is equal to Re-routing some of the flow of commodity 3 from path (b, z, c) to path (b, x, y, c) decrease the overall maximum edge congestion. Re-routing some of the flow of commodity 3 from path (b, x, y, c) to path (b, z, c) decrease the overall maximum edge congestion. Re-routing some of the flow of commodity 3 from path (b, x, y, c) to path (b, a, y, c) may decrease the overall maximum edge congestion. The best improvement obtained this way is achieved by re-routing units of commodity 3 from path (b, x, y, c) to path (b, a, y, c). Considering the new flow (obtained by this re-routing of commodity 3) and the edges between the subsets of vertices {b, x, z} and {a, c, y}, we conclude that this new flow minimizes the overall maximum edge congestion. 5/12 7/16 9/20 1/2 9/16 5/8 3/2 1 may cannot 0.25 0.50 0.75 1.00 || 1.25 1.50 can cannot 6 X