. Let (G, s, t, c) be a flow network, G = (V, E). A directed...

Transcribed Image Text:

. Let (G, s, t, c) be a flow network, G = (V, E). A directed edge e = (u, v) is called always full if f(e) = c(e) for all maximum flows f; it is called sometimes full if f(e) = c(e) for some but not all maximum flows; it is called never full if f(e) < c(e) for all maximum flows. Let (S, V \ S be a cut. That is, & € S, t € V \ S. We say the edge e = (u, v) is crossing the cut if u € S and v € V\ S. We say e is always crossing if it crosses every minimum cut; sometimes crossing if it crosses some, but not all minimum cuts; never crossing if it crosses no minimum cut. For example, look at this flow network: e: 1 f:2 h:1 S g:1 The edges e, g are sometimes full and never crossing: f is never full and never crossing; h is always full and always crossing. Alright, now it's your turn. Consider this network: с h a e S t 6 d 9 2 The fat edge a has capcity 2, all other edges have capacity 1. Let a be the number of always full edges, y that of sometimes full edges, z that of never full edges. Determine what these numbers are and enter 100x+10y + z as the answer. For example, if (x, y, z) = (2, 3, 4), answer 234; if (x, y, z) = (0, 4, 5), answer 45; if (x, y, z) = (0, 0, 9), answer 9. . Let (G, s, t, c) be a flow network, G = (V, E). A directed edge e = (u, v) is called always full if f(e) = c(e) for all maximum flows f; it is called sometimes full if f(e) = c(e) for some but not all maximum flows; it is called never full if f(e) < c(e) for all maximum flows. Let (S, V \ S be a cut. That is, & € S, t € V \ S. We say the edge e = (u, v) is crossing the cut if u € S and v € V\ S. We say e is always crossing if it crosses every minimum cut; sometimes crossing if it crosses some, but not all minimum cuts; never crossing if it crosses no minimum cut. For example, look at this flow network: e: 1 f:2 h:1 S g:1 The edges e, g are sometimes full and never crossing: f is never full and never crossing; h is always full and always crossing. Alright, now it's your turn. Consider this network: с h a e S t 6 d 9 2 The fat edge a has capcity 2, all other edges have capacity 1. Let a be the number of always full edges, y that of sometimes full edges, z that of never full edges. Determine what these numbers are and enter 100x+10y + z as the answer. For example, if (x, y, z) = (2, 3, 4), answer 234; if (x, y, z) = (0, 4, 5), answer 45; if (x, y, z) = (0, 0, 9), answer 9.

Answer rating: 100% (QA)

Solution 1 Max Flow The maximum possible flow from Sources to Targett such ... View the full answer