In the graph below, show an (s, t)-cut with capacity 4. show the nodes in S...

Transcribed Image Text:

In the graph below, show an (s, t)-cut with capacity 4. show the nodes in S show the four edges (each of capacity one) that cross the (S,T) boundary (note: edges from S to T only, not the reverse) - note that the edges from L to R have capacity co do not change that This is the flow problem that would solve a max-matching problem for the bipartite graph from the class slides (which is an example from KT). One way to find the cut is to look at the flow that corresponds to a max-matching, determine the residual graph, and then find the nodes reachable fron s. G' In the graph below, show an (s, t)-cut with capacity 4. show the nodes in S show the four edges (each of capacity one) that cross the (S,T) boundary (note: edges from S to T only, not the reverse) - note that the edges from L to R have capacity co do not change that This is the flow problem that would solve a max-matching problem for the bipartite graph from the class slides (which is an example from KT). One way to find the cut is to look at the flow that corresponds to a max-matching, determine the residual graph, and then find the nodes reachable fron s. G'