Flow Graph

Flow Graph is a #202204112118 that depicts the networking flow. The starting node is called a source (denoted \(s\)) whereas the ending node is called a sink (denoted \(t\)). Each edge has flow value (how many have flowed through) and maximum capacity (how much can flowed through), usually written in the format flow value/maximum capacity.

flow-graph

The maximum capacity for an edge must not be negative. The flow value for the edge should be less than or equal to the maximum capacity that it can allow, and the flow value from every edge must be initialised to 0 before the #calculation.

Somtimes, it will be incorporated into 202206091605#.

Links to this page
  • Residual Graph

    Residual Graph is a #202204112118 which include #202206091453 and 202206091616#.

  • Residual Edge

    Residual Edge is an edge which flow to the opposite of the flow edge#. Similar to the flow edge, it has both flow value and maximum capacity in the format of flow value/maximum capacity. However, it is initialised to 0/0 unlike its counterpart.

    The sole existence of Residual Edge is to undo or revert bad #202206091601 which doesn’t lead to #maximum flow. The Residual Edge is valid to be included into the augmentation in the later iteration (the edge has been taken at least once). When reverting, add the flow value of the residual edge to the flow edge. It is to avoid having a negative remaining capacity# (the difference of the flow edge’s maximum capacity and flow value).

  • Maximum Flow Problem

    Maximum Flow Problem ask: With an infinite input source (denoted \(s\)), how much flow can we push to through the network (depicted as 202206091453#), that is to the end node (sometime call sink, denoted \(t\)), given that each edge has a certain capacity (that one should not exceed)? *

#graph #networking