Please enable JavaScript.

Coggle requires JavaScript to display documents.

Network Flow (General (Definitions (Residual Graph: (Given a flow and a…

- - - - The edges represent the capacity of the incoming and/or outgoing flow
        The nodes represent locations where the flow ends up or starts
    - - We add all the forward and backward edges
        
        Forward Edge
        
        If we have an edge where we're not using all of its capacity we can try and push the remaining units
        
        For example if (s,u) only used 12 of the 20 then the forward edge in the residual graph would be 8
        
        Backward Edge
        
        For each edge in G we can go the opposite direction to undo some flow
        
        An example of this would be if we went from (s,u) to (u,t) we could "undo" or push backward 10 units from (t,v) if in some case it would cause us to add more flow
      - Residual capacity
        
        The capacity of an edge in the residual graph
  - - - Capacity Condition
        
        For each element in E it has to be non-zero and there's a cap to how large that number can be
        \(0 \le f(e) \le c_e\)
      - Conservation Condition
        
        The incoming flow = The outgoing flow
        
        Think of this in terms of physics
        If we had two pipes of water flowing into a single pipe, at the end of the single pipe we're flowing the sum of the 2 inputs
        
        \(\sum_\text{e into v} f(e) = \Sigma_\text{e into v} f(e)\)
    - - No outgoing flow can come from the sink
        No incoming flow can come from the source
        
        In the diagram s is the source and t is the sink
        Notice that there are no incoming to s and no outgoing from t
- - - - The edges represent the maximum capacity
    - - So we push all 20 units of (s,u).
        When we reach u we see that (u,v) would allow us to carry that flow of 20 since its capacity is 30
        Finally from that 20 sent through (u,v) we can send it through (v,t)
        
        The maximum is in fact 30 for this diagram
- - - - Two paths are edge-disjoint if they have no edge in common
- - - - The bottleneck capacity refers to the minimum residual capacity in the residual graph
- - - - The capacity of the cut is just the sum of the edges that connect A to B
        
        Note we do only the edges from A -> B
        
        A is the dark colored nodes
        B is the white colored nodes
    - - The value of any flow has a max of being its capacity
        
        Let f be any s-t flow, and (A, B) any s-t cut. Then ν(f) = \(f_{out}(A) − f_{in}(A)\)
        
        Let f be any s-t flow, and (A, B) any s-t cut. Then ν(f) ≤ c(A, B).
      - If f is an s-t-flow such that there is no s-t path in the residual graph Gf ,then there is an s-t cut (A∗, B∗) in G for which ν(f) = c(A∗, B∗). Consequently, f has the maximum value of any flow in G, and (A∗, B∗) has the minimum capacity of any s-t cut in G.