ANONYMOUS wrote:
> Hi there! It's me with my lecture questions again. I tried rewatching the lectures and going to a lab facilitator to ask but they were confused too so I have a few questions this time:
>
> 1. In the Ford-Fulkerson problem slide (slide 18) is it the case that it will just repeat the path {s, a, b, t} and {s, b, a, t} over and over again or is this just a worst case scenario. If not, why would it take that path instead of the shorter {s, a, t} and {s, b, t}.
This is the worst case scenario. Note that Ford-Fulkerson just uses a DFS and provides no guarantees about how it will select a path, so we must consider the worst case. Finding strategies (such as taking the shortest available path) and proving that this gives better bounds is exactly what we then do with Edmonds-Karp!
> 2. For Edmonds-Karp (slide 21), could you explain what the "ladder" meant ? Is it because if we saturate u v, we can only use v u to release u v and it repeats over and over like the Ford-Fulkerson problem slide? (i.e. it keeps getting longer and longer because you now can't go through u but must go through v)? A diagram would help alot!
You are exactly correct. As described in the lecture, once the (u, v) edge is saturated, the only way to unsaturate it is to use (v, u), and vice versa. You are right that this will repeat with the path getting longer and longer. This is exactly what gives us a limit on number of augmenting paths for Edmonds-Karp, as we know there is an upper bound on the length of a path: V
> 3. For cut flow (slide 26), how is it that sum V f(u, v) = 0?
f(u, v) is the net flow from u to v across the edge connecting them. For any vertex u (other than s or t), the net incoming flow and outgoing flow must exactly balance to zero, by definition.
> Thanks for the help for my previous questions, Gozz and Max, you have been really helpful for my understanding!
