1
$\begingroup$

I am learning about the Ford Fulkerson algorithm, but having a hard time getting an intuitive feel for what a "flow" is. Is the "flow" the amount that travels between two adjacent nodes on a graph? Or the an amount that travels down a path in the graph (like from the source to the sink)?

$\endgroup$

1 Answer 1

0
$\begingroup$

Formally, a flow is a map from edges to amounts which satisfies some additional constraints, like for all inner nodes the incoming flow equals the outgoing flow, more formally expressed the flow associated with all incoming arcs equals that associated with all outgoing arcs.

So the flow of a single edge would be one item of that map, and would describe the amount that travels between adjacent nodes. The overall flow is not only the amount along a given path, but the information for the whole graph about what amounts travel along what edges. Of course, if you were to know the flow for each edge, or for each path, then you do know the complete flow as well.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .