Question

Let (G, s, t, c) be a flow network G = (V, E), A directed edge e = (m u) is called always fu ir f(e) e(e) forall maximum fiows f: it is called sometimes fullit f(e)for some but not all maximum flows: it is caled never fulit f(e) <c(e) for all maximum flows. Let (S, V S be a cut. That is, s E S,teV S. We say the edge u, ) is crossing the cut ifu E SandrEV\ 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 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: An edgee can be () always fuil. ty) sometimes full, () never fult it can be () aways crossing (y) sometimes crossing, (z) never crossing So there are nine possible combinations: (ox) always full and always crossing, by) always full and sometimes crossing, and so on. Or are there? Maybe some possibities are impossible. Lets draw a table: The edge e is: always full sometimer full tPossible f 2 Possible always crossing or or impossible?impossible? Possible or impossible? Possible or impossible? sometimes crossing s Possible or impossible? impossible? impossible? crossing Possible or Take a piece of paper, complete the 3 x 3 table below by either finding an example llustrating that the combination is possible ar by concluding that it is impossible. To do so, you will need the Max Flow Min Cut Theorem plus a bit of your own thinking. Once you have completed the table, select which of the following statements are true: There is a flovw network and an edge e that is... □ always rulland always crossing. □ always fulland sometimes crossing aways full and never crossing. □ sometimes full and always crossing sometimes full and sometimes crossing sometimes full and never crossing □ never full and always crossing never full and sometimes crossing. never full and never crossing.

Answer 1

"Maximum flow: The maximum possible flow from Sources to Target (t) Such that no edge exceeds its capacity. Since max flow for given network 1. The edge �alpha� is never reaches its capacity. always full edges: (e) Sometimes full edges: (b, c, d, f, g, h, i) never full edges: (a) x (always full edges) = 1 y (Sometimes full edges) = 7 z (never full edges) = 1 100 times + 10y + z = 100 times 1 + 10 + 7 + 1 = 171 (2) Minimum cut: ""It & the minimum Sum of weights of edges. When removed from the graph. Splits the graph in two groups"". an given graph only one minimum cut is possible. Which occurs if edge �e� is removed (min cut = 1) always crossing edges: {e} Sometimes Crossing edges: {} never crossing edges: {a, b, c, d, f, g, h, i}"